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