The first step of a proof by induction is to:

prove the statement for the first value, usually $n = 1$

assume the statement is true for all $n$

Why does checking many examples not prove a statement?

induction does not use examples

Proof by Mathematical Induction | HSC Maths Extension 1

In short: Mathematical induction proves a statement for every whole number in two steps. First, prove it is true for the first value. Then show that if it is true for $n = k$ , it must also be true for $n = k + 1$ , so it is true for all of them.

Starting point: what you already know

Sigma notation: $k = 1 \sum n k = 1 + 2 + \dots + n$ .
From arithmetic series: $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ .
Divisible by 3 means equal to $3 M$ for some whole number $M$ .
Algebra skills: factorising, expanding, finding a common denominator.

Why we need proof

The pattern $1 = 1^{2}$ , $1 + 3 = 2^{2}$ , $1 + 3 + 5 = 3^{2}$ suggests that the first $n$ odd numbers add to $n^{2}$ . Checking more examples makes it believable, but checking a million cases still does not prove it for the next one. Induction proves it for every $n$ at once.

The structure

Let $P (n)$ be the statement you want to prove.

The assumption in step 2 is called the inductive hypothesis. You are not assuming what you want to prove. You are proving "if it works for one domino, it works for the next".

Proving sums

Proving divisibility

Mathematical induction

Idea

First domino falls
Each one knocks the next

Steps

Base case n = 1
Assume true for n = k
Prove for n = k + 1
Write the conclusion

Sums

Add the next term to both sides

Divisibility

Write as divisor × M
Substitute and factor

Errors

No base case
Inductive step fails

Year 12A harder sum

Prove $r = 1 \sum n r^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$ .

Base case: $1 = \frac{1 \cdot 2 \cdot 3}{6}$ . True.

Step. Assume $r = 1 \sum k r^{2} = \frac{k ( k + 1 ) ( 2 k + 1 )}{6}$ . Then $r = 1 \sum k + 1 r^{2} = \frac{k ( k + 1 ) ( 2 k + 1 )}{6} + (k + 1)^{2} = \frac{( k + 1 ) [ k ( 2 k + 1 ) + 6 ( k + 1 ) ]}{6}$ $= \frac{( k + 1 ) ( 2 k ^{2} + 7 k + 6 )}{6} = \frac{( k + 1 ) ( k + 2 ) ( 2 k + 3 )}{6}$ which is the formula with $n = k + 1$ . Tip: take out the common factor $(k + 1)$ early instead of expanding everything.

Fractions. For $\sum_{r = 1}^{n} \frac{1}{r ( r + 1 )} = \frac{n}{n + 1}$ , the step is $\frac{k}{k + 1} + \frac{1}{( k + 1 ) ( k + 2 )} = \frac{k ( k + 2 ) + 1}{( k + 1 ) ( k + 2 )} = \frac{( k + 1 ) ^{2}}{( k + 1 ) ( k + 2 )} = \frac{k + 1}{k + 2}$ . Use the common denominator, then factorise the top. With factorials, write both fractions over the larger factorial, using $(k + 3)! = (k + 3) (k + 2)!$ .

Inequalities. To prove $3^{n} > 2 n + 1$ for $n \geq 2$ : the base case is $9 > 5$ . Assume $3^{k} > 2 k + 1$ . Then $3^{k + 1} = 3 \times 3^{k} > 3 (2 k + 1) = 6 k + 3 > 2 k + 3 = 2 (k + 1) + 1$ , since $6 k > 2 k$ . First check small values to find where the statement starts to be true: $2^{n} > n^{2}$ fails at $n = 3$ and $n = 4$ ( $16 = 16$ ), and works from $n = 5$ .

Trig sums. In the step, a product-to-sum identity often turns the new term into a difference of squares of sines, such as $sin (2 k + 1) θ sin θ = sin^{2} (k + 1) θ - sin^{2} k θ$ .

Quick summary

Induction has two steps: prove the base case, then show that if it is true for $k$ , it is true for $k + 1$ .
For sums, add the next term to the assumed sum and simplify to the target.
For divisibility, write the assumption as divisor $\times M$ , substitute, then factor out the divisor.
Finish with the conclusion sentence. Missing either step means there is no proof.

Quiz

13 questions with instant marking. It is free, and your scores are saved to your account so you can carry on from any device.

Turn on JavaScript to sign in and take the quiz.

Try 3 questions now

The first step of a proof by induction is to:
1. A prove the statement for the first value, usually $n = 1$
2. B assume the statement is true for all $n$
3. C prove it for $n = k + 1$
4. D check 10 examples
Show answer
A: prove the statement for the first value, usually $n = 1$
This is the base case: the first domino falls.
In the inductive step you assume the statement is true for:
1. A all $n$
2. B $n = k$
3. C $n = k + 1$
4. D $n = 0$ only
Show answer
B: $n = k$
Then you show it must also be true for $n = k + 1$ .
Why does checking many examples not prove a statement?
1. A examples are always wrong
2. B the next case might still fail
3. C induction does not use examples
4. D it takes too long
Show answer
B: the next case might still fail
A pattern can hold for many cases and then break.

Proof by Mathematical Induction