Proof by Induction is used to prove statements that are true for all integers n greater than some starting value.

The idea is as follows:

1. Show manually that the statement is true for the base case n=a.

2. Show that if some arbitrary case n=k is true, then the next case n=k+1 must be true.

3. Since the base case n=a is true, then the next case n=a+1, thus the case n=a+2 is true and so on for all positive integers.

It is helpful to use the notation P(n) to represent the statement for an arbitrary integer n. This saves us writing the statement every time. Make sure you define

Our goal in a proof by induction is to show that

Therefore, by induction

so P(n) is true for all n∈Z+.

It is critical when writing proofs by induction to have a rigorous conclusion. You must show to the examiner grading your work that you understand induction. Your conclusion should clearly show:

• You have shown the base case is true

• You understand that the statement is true for n=k+1 IF it is true for n=k.

Evidence of understanding the implication is critical for earning the final mark. For example, if you say:

We have shown that the statement is true for n=k and for n=k+1 you will NOT earn the final mark.

Another common mistake is to write:

We have shown that if n=k is true then n=k+1 is true.

This does not mention the statement, and incorrectly states that n is literally equal to k and to k+1, which is impossible.