What are your favorite proofs using mathematical induction? 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.
 A: 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$.
A: 
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}
$$
A: A lot of it depends on what you consider 'cool'.


*

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

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

*[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.
