Currently unavailable: for new students
Degree: Mathematics (Masters) - Oxford, St Catherine's College University
|Maths||A Level||£20 /hr|
|Physics||A Level||£20 /hr|
|-Oxbridge Preparation-||Mentoring||£20 /hr|
|-Personal Statements-||Mentoring||£20 /hr|
Proof by Induction: The method of Proof by Induction is a simple but very powerful technique. It involves 3 steps:
1) Showing a claim is true for a basic integer value of n (e.g. 0 or 1)
2) Assuming the claim is true for n=k where k is an arbitrary integer
3) Using this assumption to show that the claim is true for n=k+1
The reason why these 3 steps prove the claim is because you've shown 2 things: You've shown that the claim's true for 0 (or 1). You've also shown that is the claim is true for n=k, then it's also true for n=k+1. And so if the claim is true for n=0 (or 1), then the claim is true for n=1(or 2). Then if the claim is true for n=1 (or 2) then it's true for n=2 (or 3) and so on. So the claim is true for all integers n greater than or equal to 0.
1) In this particular case, we'll start with n=0:
(3^0)-1 = 1-1 = 0 = 2 x 0 and so the claim holds.
2) Now let's assume the claim is true for n=k. That is, (3^k)-1 is a multiple of 2. So (3^k)-1 = 2c for some integer c.
3) Now let's look at n=k+1:
(3^(k+1))-1 = 3 x (3^k) - 1
Using our assumption, (3^k)-1 = 2c, so that (3^k)=2c+1
Now we have 3 x (2c + 1) - 1 = 6c + 3 -1 = 6c +2 = 2(3c + 1)
(3^(k+1))-1 = 2(3c + 1) and since (3c + 1) is an integer, we have proven the claim.see more