What are your favorite proofs using mathematical induction?

Question

I would like to get a list going of cool proofs using mathematical induction.

Im not really interested in the standard proofs, like $1+3+5+...+(2n-1)=n^2$, that can be found in any discrete math text. I am looking for more interesting proofs.

Thanks a lot.

Answer 1

A lot of it depends on what you consider 'cool'.

1. For $n\geq 3$, $n^{n+1} > (n+1)^n$.
   This requires some ingenuity in dealing with the inequality. Straight forward approaches tend to not work.

2. A square can be dissected into $ n \geq 6$ (not necessarily congruent) squares.
   This is a good puzzle to introduce non-stanard induction.

3. [Martin Gardner] There are $n$ cars on a circular track, and amongst them there is enough gas for 1 car to make a complete loop around the track. Show that there is 1 car that can make it completely around the track by pooling gas from every car that it passes by.
   Yes I am aware that most approach this not via induction.

Answer 2

You can prove by induction that $\sqrt{2}$ is irrational. We show $$\left(\frac{p}{q}\right)^2\neq 2$$ for $p,q\in\mathbb N$ by induction on $q$.

Assume $(p/q)^2\neq 2$ for all $p,q\in\mathbb N$ and $q<n$. Then we show that $(p/n)^2\neq 2$ for all $p$ by contradiction.

If $(p/n)^2 = 2$, then we show that $0<p-n<n$ and $$\left(\frac{2n-p}{p-n}\right)^2=2$$

This contradicts the induction hypothesis.

I've obviously skipped the base case, $q=1$.

Answer 3

Let $a>0$ and $d\in\mathbb{N}$ and define the simplex $S_d(a)$ in $\mathbb{R}^d$ by $$ S_d(a)=\{(x_1,\ldots,x_n)\in\mathbb{R}^d\mid x_1,\ldots,x_d\geq 0,\;\sum_{i=1}^d x_i\leq a\}. $$ Then for every $a>0$ and $d\in\mathbb{N}$ we get the following $$ \lambda_d(S_d(a))=\frac{a^d}{d!},\qquad (*) $$ where $\lambda_d$ is the $d$-dimensional Lebesgue measure.

Proof: Let $d=1$. Then $$ \lambda_1(S_1(a))=\lambda_1([0,a])=a=\frac{a^1}{1!}, $$ so this case holds. Assume $(*)$ holds for $d\in\mathbb{N}$ and let us prove that it also holds for $d+1$. Now we use that for $B\in\mathcal{B}(\mathbb{R}^{n+m})$ the following holds: $$ \lambda_{n+m}(B)=\int_{\mathbb{R}^n}\lambda_m(B_x)\,\lambda_n(\mathrm dx), $$ where $B_x=\{y\in \mathbb{R}^m\mid (x,y)\in B\}$. Using this we have $$ \lambda_{d+1}(S_{d+1}(a))=\int_{\mathbb{R}}\lambda_d((S_{d+1}(a))_{x_1})\,\lambda_1(\mathrm dx_1). $$ But $$ \begin{align} (S_{d+1}(a))_{x_1}&=\{(x_2,\ldots,x_{d+1})\in\mathbb{R}^d\mid (x_1,x_2,\ldots,x_{d+1})\in S_d(a)\}\\ &=\{(x_2,\ldots,x_{d+1})\in\mathbb{R}^d\mid x_1,x_2,\ldots,x_{d+1}\geq 0,\; x_2+\cdots+ x_{d+1}\leq a-x_1\}\\ &= \begin{cases} S_{d}(a-x_1)\quad &\text{if }0\leq x_1\leq a,\\ \emptyset &\text{otherwise}. \end{cases} \end{align} $$ Thus $$ \begin{align} \lambda_{d+1}(S_{d+1}(a))&=\int_0^a\lambda_d(S_d(a-x_1))\,\lambda_1(\mathrm dx_1)=\int_0^a\frac{(a-x_1)^d}{d!}\,\lambda_1(\mathrm dx_1)\\ &=\frac{1}{d!}\left[-\frac{1}{d+1}(a-x_1)^{d+1}\right]_0^a=\frac{a^{d+1}}{(d+1)!}. \end{align} $$