Favourite proofs by induction?

I am searching for nice proofs by induction, that can be used to teach. I remember this example, that my analysis professor presented to us in first semester and I am searching for more such easily understood examples.

Theorem: A chess-board with side length $2^n$ for $n \in \mathbb{N}$, where one square in the corner is cut off (see picture for $n=2$), can be tessellated by pieces consisting of 3 squares in an L-shape (see picture).

Proof: By induction. For $n=1$, the piece and the board have the same shape. For $n>1$, the board having side lengt $2^n$, divide it into 4 such boards with side length $2^{n-1}$, where one of those smaller boards has its cut-off corner in the corner of the bigger board and the other three have their cut-off corner in the center of the bigger board, leaving 3 pieces in the center, which can be filled by one more L-piece.

• – quid Oct 20 '14 at 10:45
• This question might interest you. – Git Gud Oct 20 '14 at 10:46
• I always liked the proof of $\frac{d}{dx} x^n = nx^{n-1}$ using induction. It's easy and prettier (to my taste) than using Newton's Binomium. – Krijn Oct 20 '14 at 10:50
• I like the proof of the Fibonacci matrix identity. Very simple but nice. – John Smith Oct 20 '14 at 11:07