What are your favorite proofs using mathematical induction? [closed]

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.

-

closed as not constructive by Thomas, Henning Makholm, rschwieb, Norbert, SeiriosFeb 14 '13 at 21:25

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

I like the joke proof that all numbers are a whole lot less than a million. :) – Thomas Andrews Feb 14 '13 at 19:55
I assume you tagged it as "set theory" rather than something else because you want to allow transfinite induction? – Thomas Andrews Feb 14 '13 at 19:56
Try Googling "Example of mathematical induction". – Fly by Night Feb 14 '13 at 19:56
@user43666 This might interest you. – Git Gud Feb 14 '13 at 19:57
I you start from Peano Arithmetic, pretty much everything that can be proved is ultimately by induction. – Henning Makholm Feb 14 '13 at 20:18

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.

-
3 is correct even if there is an infinitude of cars? – Lior B-S Feb 14 '13 at 21:17

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$.

-

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 have that $$\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}

-