The principle of induction

Sequences and induction, grade 11 (5 units) Lesson 17 of 23Learning

The principle of induction

Examples are not a proof

Let us check the expression $\displaystyle n^2+n+41$ for $\displaystyle {n}={1, 2, 3, \ldots}$ : we get $\displaystyle 43, 47, 53, 61, 71, \ldots$ – all prime numbers. So it goes on up to $\displaystyle {n}={39}$ .

Is $\displaystyle n^2+n+41$ prime for every natural $\displaystyle n$ ? No: for $\displaystyle {n}={40}$ we get $\displaystyle {1600+40+41}={1681}={41^2}$ .
39 examples supported the guess, and still it is false.
A claim about all the natural numbers – infinitely many cases – cannot be proved by checking cases. It takes another method.

A row of dominoes

An endless row of dominoes stands one after another. To know that they all fall, it is enough to know two things:

the first domino falls;
every domino that falls knocks over the next one.

Then the first knocks over the second, the second the third, and so every domino falls in the end. If either of the two is missing there is no certainty: maybe none falls, maybe there is a gap in the middle of the row.

The three parts of the proof

A proof by mathematical induction of a claim for every natural $\displaystyle n$ :

The base case – prove that the claim holds for $\displaystyle {n}={1}$ .
The inductive step – assume that the claim holds for some natural number $\displaystyle k$ (the induction hypothesis), and prove that it holds for $\displaystyle k+1$ too.
The conclusion – by the principle of induction, the claim holds for every natural $\displaystyle n$ .

Every proof is written in these three parts, each named.

A proof: the sum of the odd numbers

The picture shows that $\displaystyle {1+3+5+7+9}={5^2}$ : each L-shaped layer turns a $\displaystyle k$ by $\displaystyle k$ square into a $\displaystyle k+1$ by $\displaystyle k+1$ square, and holds $\displaystyle 2k+1$ squares. This is exactly the inductive step of the proof below, which proves by induction that

1+3+5+\ldots+(2n-1)=n^2

for every natural $\displaystyle n$ . Press “Show the proof”, and go on step by step:

	Claim	Reason
1	For $\displaystyle {n}={1}$ : $\displaystyle {1}={1^2}$	Base case
2	$\displaystyle {1+3+\ldots+(2k-1)}={k^2}$	The induction hypothesis, for some natural $\displaystyle k$
3	To prove: $\displaystyle {1+3+\ldots+(2k-1)+(2k+1)}={(k+1)^2}$	The claim for $\displaystyle k+1$ ; the $\displaystyle (k+1)$ th term is $\displaystyle {2(k+1)-1}={2k+1}$
4	$\displaystyle {1+3+\ldots+(2k-1)+(2k+1)}={k^2+(2k+1)}$	By the induction hypothesis (2)
5	$\displaystyle {k^2+2k+1}={(k+1)^2}$	The square of a sum; (3) is proved
6	$\displaystyle {1+3+\ldots+(2n-1)}={n^2}$ for every natural $\displaystyle n$	Conclusion: (1), (2)–(5) and the principle of induction

A hypothesis against a claim

The induction hypothesis looks like the claim, but it is a different statement:

The claim: “for every natural $\displaystyle n$ , $\displaystyle {1+3+\ldots+(2n-1)}={n^2}$ ” – this is what is proved.
The hypothesis: “for a certain $\displaystyle k$ , $\displaystyle {1+3+\ldots+(2k-1)}={k^2}$ ” – it is only part of the inductive step, which proves a statement of the form “if the claim holds for $\displaystyle k$ , then it holds for $\displaystyle k+1$ ”.
Proving “if … then …” does not need to know whether the hypothesis is true: it is assumed as a working tool, not as a fact.
Both parts are needed, and neither follows from the other: the base without the step is one example, and the step without the base is a chain with no beginning.

Tiling boards

Board $\displaystyle n$ is a square of $\displaystyle 2^n$ by $\displaystyle 2^n$ squares with its lower-left square missing. We prove by induction that every such board can be tiled with L shapes of three squares (board 1).

Base case: board 1 is itself an L shape.
Inductive step: assume that board $\displaystyle k$ can be tiled. Split board $\displaystyle k+1$ into four squares of $\displaystyle 2^k$ by $\displaystyle 2^k$ . The lower-left square has a corner missing – it is board $\displaystyle k$ . On the other three put one L shape in the middle of the board, so that it covers, in each of them, the corner facing the middle. Now each of them is board $\displaystyle k$ (turned), and by the hypothesis it can be tiled.
Conclusion: by the principle of induction, board $\displaystyle n$ can be tiled for every natural $\displaystyle n$ .

Exercise 1

$\displaystyle {2+4+6+\ldots+2n}={n(n+1)}$
Prove by induction that the claim holds for every natural $\displaystyle n$ .

Base case

Check the claim for $\displaystyle {n}={1}$ .

Inductive step

Write the induction hypothesis – the claim for some natural $\displaystyle k$ – and what must be proved for $\displaystyle k+1$ .

The working: start from the expression you got after putting in the hypothesis, and reach what must be proved.

/ – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – check and a new line · * – times · ^ – power, ↓ – end of the power

/ – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

Conclusion

Exercise 2

How many L shapes are in the tiling of board 3 (8 by 8 squares, one missing)? And of board $\displaystyle n$ ? Write the working for board 3.

/ – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

Exercise 3

Noa checked $\displaystyle n^2-n+11$ for $\displaystyle {n}={1, 2, \ldots, 10}$ , and got only prime numbers.
She claims that the expression is prime for every natural $\displaystyle n$ . Is she right? Explain.

Formulas: sequences and induction, grade 11 (5 units)

Open as a page

A sequence and the sum of its first terms

The term from the sum – $\displaystyle S_n$ the sum of the first $\displaystyle n$ terms
$\displaystyle a_n$ $\displaystyle =$ $\displaystyle S_n-S_{n-1}$ $\displaystyle n\geq2$
The first term is the sum of one term
$\displaystyle a_1$ $\displaystyle =$ $\displaystyle S_1$

The arithmetic sequence

The recursion rule – $\displaystyle d$ the common difference
$\displaystyle a_{n+1}=a_n+d$
The general term
$\displaystyle a_n$ $\displaystyle =$ $\displaystyle a_1+(n-1)d$
The arithmetic mean of the neighbours
$\displaystyle a_n$ $\displaystyle =$ $\displaystyle \frac{a_{n-1}+a_{n+1}}{2}$ $\displaystyle n\geq2$
The sum of the first $\displaystyle n$ terms
$\displaystyle S_n$ $\displaystyle =$ $\displaystyle \frac{n(a_1+a_n)}{2}$
The sum without the last term
$\displaystyle S_n$ $\displaystyle =$ $\displaystyle \frac{n\left[2a_1+(n-1)d\right]}{2}$

The geometric sequence

The recursion rule – $\displaystyle q$ the common ratio
$\displaystyle a_{n+1}=a_n\cdot q$
The general term
$\displaystyle a_n$ $\displaystyle =$ $\displaystyle a_1\cdot q^{n-1}$
The geometric mean: a term’s square is the product of its neighbours
$\displaystyle a_n^2$ $\displaystyle =$ $\displaystyle a_{n-1}\cdot a_{n+1}$ $\displaystyle n\geq2$
The sum of the first $\displaystyle n$ terms
$\displaystyle S_n$ $\displaystyle =$ $\displaystyle \frac{a_1(q^n-1)}{q-1}$ $\displaystyle q\neq1$

The infinite geometric sequence

The sum of a convergent sequence
$\displaystyle S$ $\displaystyle =$ $\displaystyle \frac{a_1}{1-q}$ $\displaystyle -1<q<1,\ q\neq0$

The laws of powers

A product of powers of one base
$\displaystyle a^m\cdot a^n$ $\displaystyle =$ $\displaystyle a^{m+n}$
A quotient of powers of one base
$\displaystyle \frac{a^m}{a^n}$ $\displaystyle =$ $\displaystyle a^{m-n}$ $\displaystyle a\neq0$
A power of a power
$\displaystyle \left(a^m\right)^n$ $\displaystyle =$ $\displaystyle a^{mn}$
A power with exponent 0
$\displaystyle a^0$ $\displaystyle =$ $\displaystyle 1$ $\displaystyle a\neq0$
A power with a negative exponent
$\displaystyle a^{-n}$ $\displaystyle =$ $\displaystyle \frac{1}{a^n}$ $\displaystyle a\neq0$

Sums proved by induction

The sum of the natural numbers
$\displaystyle 1+2+3+\ldots+n$ $\displaystyle =$ $\displaystyle \frac{n(n+1)}{2}$
The sum of the odd numbers
$\displaystyle 1+3+5+\ldots+(2n-1)$ $\displaystyle =$ $\displaystyle n^2$
The sum of the squares
$\displaystyle 1^2+2^2+3^2+\ldots+n^2$ $\displaystyle =$ $\displaystyle \frac{n(n+1)(2n+1)}{6}$
The sum of the cubes
$\displaystyle 1^3+2^3+3^3+\ldots+n^3$ $\displaystyle =$ $\displaystyle \frac{n^2(n+1)^2}{4}$