Core Pure 8: Proof By Induction

Question 1

What are the 4 Steps for Proof by Induction

Answer 1

Step 1: Basis
Prove the general statement is true for n=1

Step 2: Assumption
Assume the general statement is true for n=k

Step 3: Inductive
Show that the general statement is then true for n=k+1

Step 4: Conclusion
The general statement is then true for all positive integers, n.

Question 2

How do you do Step 1: Basis Step

Answer 2

Substitute n = 1 into both the LHS and RHS of the formula to check if the formula works for n = 1

Question 3

How do you do Step 2: Assumption

Answer 3

In this step you assume that the general statement given is true for n=k

Question 4

How do you do Step 3: Inductive Step

Answer 4

• Sum k to terms plus the (k+1)th term
• This is the (k+1)th term
• Sum of first k terms is k^2 by assumption
• This is the same expression as n^2 with n replaced by k+1

Question 5

How do you do Step 4: Conclusion Step

Answer 5

Result is true for n =1 and steps 2 and 3 imply result is true for n = 2. Continuing to apply steps 2 and 3 implies the result is true for n = 3, 4, 5, e.c.t