Link to slides

The principle of mathematical induction

Version using dominoes

Consider a row of dominoes.

Suppose that two conditions are satisfied:

1. You knocked over the first domino.
2. Whenever some domino falls, it knocks over the next one.

Then all dominoes fall eventually.

Source

Example

Let's use mathematical induction to prove that

\[1 + 2 + \dotsb + n = \frac{n(n+1)}2 \qquad \left( = \binom{n+1}2\right)\]

for each \(n = 1,2,\dotsc\)

We take \(\mathrm{Claim}(n)\) to be the statement \(1+2+\dotsb+n = \frac{n(n+1)}2\).

Base case:

\(1 = \frac{1 (1+1)}2\) so \(\mathrm{Claim}(1)\) is true.

Induction step:

Suppose that \(\mathrm{Claim}(n)\) is true for some \(n\).

That is, \(1 + 2 + \dotsb + n = \frac{n(n+1)}2\).

We seek to show that \(\mathrm{Claim}(n+1)\) is also true.

Let's compute:

\[\begin{aligned}\text{LHS of } \mathrm{Claim}(n+1) & = 1 + \dotsb + (n+1)\\&={(1+\dotsb + n)} + (n+1) \\ & = \frac{n(n+1)}2 + (n+1)\\ & = \frac{n(n+1)}2 + \frac{2n+2}2\\ & = \frac{n^2 + 3n+2}2 \\& = \frac{(n+1)(n+2)}2 = \text{RHS of }\mathrm{Claim}(n+1)\end{aligned}\]

Hence, \(\mathrm{Claim}(n+1)\) is true too.

We conclude that, by induction, \(\mathrm{Claim}(n)\) is true for all \(n=1,2,\dotsc\).

Problem: Produce a "closed formula" for

\[1^2 + \dotsb+ n^2.\]

Let's first compute some values:

\[\begin{array}{r|l}n & 1^2+\dotsb + n^2 \\ \hline 1 & 1 \\ \hline 2 & 5 = 1 + 4 \\ \hline 3 & 14 = 1 + 4 + 9 \\ \hline 4 & 30 = 14 + 16 \\ \hline 5 & 55 = 30 + 25 \\ \hline 6 & 91 = 55 + 36\end{array}\]

Inspiration, coffee, or Lagrange polynomials suggest that perhaps

\[1^2 + \dotsb + n^2 = \frac{n(n+1)(2n+1)}6.\]

Exercise: Use induction to prove this! ("Guess and verify")

Proving \(1^2 + \dotsb + n^2 = \frac{n(n+1)(2n+1)}6\)

Base case:

\(1^2 = \frac {1\cdotp 2 \cdotp 3}6\)

Induction step \(n \to n+1\):

\[\begin{aligned}1^2 + \dotsb + (n+1)^2 & = (1^2 + \dotsb + n^2) + (n^2 + 2n+1) \\ & = \frac{n(n+1)(2n+1)}6 + \frac{6n^2+12n+6}6\\&= \frac{2n^3 + 9n^2 + 13n+6}6 \\ & = \frac{(n+1)(n+2)(2(n+1)+1)}6\end{aligned}.\]

We could go on! For example,

\[1^3 + \dotsb + n^3 = \frac{n^2(n+1)^2}4 = (1^2 + \dotsb + n^2)^2.\]

General case: Faulhaber's formula for \(1^p + \dotsb + n^p\).

Remark

"Real-life" proofs by induction are often less straightforward than what we did so far.

For example, we may need to prove stronger claims (than what we're really after) for the induction step to work.

Example

We may now use induction to finally prove that

\[ \frac 1 2 + \frac 1 4 + \dotsb + \frac 1 {2^n} < 1\]

for \(n = 1,2,\dotsc\).

First attempt

\(\mathrm{Claim}(n)\colon \frac 1 2 + \dotsb + \frac 1{2^n} < 1\).

Base case: \(\mathrm{Claim}(1)\) is true because \(\frac 1 2 < 1\).

Induction step: Suppose that \(\mathrm{Claim}(n)\) is true. In other words, \(\frac 1 2 + \dotsb + \frac 1{2^n} < 1\). We need to show that \(\frac 1 2 + \dotsb + \frac 1{2^{n+1}} < 1\).

We compute:

\[\begin{aligned}\frac 1 2 + \dotsb + \frac 1{2^{n+1}} &= \underbrace{\frac 1 2 + \dotsb + \frac 1{2^n}}_{<1 \text{ by assumption}} + \frac 1{2^{n+1}}\\& < 1 + \frac 1{2^{n+1}}\end{aligned}.\]

Not good enough! What can we do?

Second attempt

Inspired by the sequence \(\frac 1 2, \frac 3 4, \frac 7 8, \dotsc\) we try to prove

\[\mathrm{Claim}'(n)\colon \frac 1 2 + \dotsb + \frac 1{2^n} = 1 - \frac 1 {2^n}.\]

Base case: \(\frac 1 2 = 1 - \frac 1 2\) so  \(\mathrm{Claim}'(1)\) is true.

Induction step: Suppose that \(\frac 1 2 + \dotsb + \frac 1 {2^n} = 1 - \frac 1 {2^n}\). Then:

\[\begin{aligned}\frac 1 2 + \dotsb + \frac 1{2^{n+1}} &= {\frac 1 2 + \dotsb + \frac 1{2^n}} + \frac 1{2^{n+1}}\\& =  1 - \frac 1 {2^n} + \frac 1{2^{n+1}} = 1 - \frac 2{2^{n+1}} + \frac 1 {2^{n+1}}\\& = 1 - \frac 1 {2^{n+1}}.\end{aligned}.\]

Hence, \(\frac 1 2 + \dotsb + \frac 1 {2^n} = 1 - \frac 1{2^{n}} < 1\) for each \(n = 1,2,\dotsc\)

Problem

Show that

\[ 1 + \frac 1 {2^2} + \frac 1 {3^2} + \dotsb + \frac 1 {n^2} < 2\]

for each \(n = 1,2,\dotsc\)

Solution (sketch)

We use induction to show that

\[ 1 + \frac 1 {2^2} + \frac 1 {3^2} + \dotsb + \frac 1 {n^2} \leqslant 2 - \frac 1 n\]

for each \(n = 1,2,\dotsc\)

Note that

\[\begin{aligned}&& 2-\frac 1 n + \frac 1{(n+1)^2} & \leqslant 2 - \frac 1 {n+1} \\&\Leftrightarrow&\frac 1 {n+1} + \frac 1{(n+1)^2} & \leqslant \frac 1 n\\&\Leftrightarrow&n(n+1)+n&\leqslant(n+1)^2\\&\Leftrightarrow&0 &\leqslant 1.\end{aligned}\]

Geometric applications of induction

A \(2\times 2\) board with one square removed is called an L-shape.

Classical problem

Consider tilings of boards using L-shapes (or other shapes such as "Tetris pieces") and subject to various restrictions.

Question

Can we always tile an \(n\times n\) board (where \(n\geqslant 2\)) using L-shapes in such a way that there is precisely one square left?

\(n=2\)

\(n=3\)

\(n=4\) or \(n = 5\)

?

Problem

Show that any \(2^n\times 2^n\) board can be tiled using L-shapes in a way that excludes just one square.