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.


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