A nice example arises by relativizing Goodstein's Theorem from $\rm\ \epsilon_0 = \omega^{\omega^{\omega^{\cdot^{\cdot^{\cdot}}}}}$ down to $\rm\ \omega^2\:.\ $
$\rm\ \omega^2\ $ Goodstein's Theorem $\ $ Given naturals $\rm\ a,\:b,\:c\ $ and an arbitrary increasing "base-bumping" function $\rm\ g(n)\ $ on $\:\mathbb N\:$ the following iteration eventually reaches $0\ $ (i.e. $\rm\ a = c = 0\:$).
$\rm\quad\quad\quad\quad\ \ a\ b + c \ \ \to\quad\quad\ \ a\ \ \ \ \ g(b)\ +\ \ \ c\ \ -\ 1\quad if\quad\ c > 0 $
$\rm\quad\quad\quad\quad\ \ \phantom{a\ b + c}\ \ \to\ \ (a-1)\ g(b)\ +\ g(b)-1\quad if\quad \ c = 0 $
Note: $\ $ The above iteration is really on triples $\rm\ (a,b,c)\ $ but I chose the above notation in order to emphasize the relationship with radix notation and with Cantor Normal form for ordinals < $\epsilon_0$. $\ \ $ For more on Goodstein's Theorem see the link in Andres's post or see my 1995\12\11 sci.math post.
Consider the simple continued fraction $\langle a_0;a_1,a_2,\dots\rangle$, where all the $a_i$ are integers, and all positive except possibly $a_0$.
Define the sequences $p_i$, $q_i$ by
$p_{-1}=0$, $p_0=a_0$, and $p_k=a_kp_{k-1}+p_{k-2}$, and
$q_{-1}=0$, $q_0=1$, and $q_k=a_kq_{k-1}+q_{k-2}$.
We want to show that $\langle a_0;a_1,\dots,a_k\rangle=\frac{p_k}{q_k}$.
The standard way to prove the result by induction is to prove the stronger result that for any positive $x$,
$$\langle a_0;a_1,\dots,a_{k-1},x\rangle=\frac{xp_{k-1}+p_{k-2}}{xq_{k-1}+q_{k-2}}.$$
As a small additional example, a recent question asked for a proof that the denominator of
$\frac{1}{\sqrt{a_1}+\sqrt{a_2}+\cdots+\sqrt{a_n}}$ can be rationalized. An induction proof used the stronger induction hypothesis that $\frac{1}{\sqrt{a_1}+\sqrt{a_2}+\cdots+\sqrt{a_n}+t}$ can be rationalized, where $t$ is a free parameter.
For early induction arguments, however, I think inequalities are quite persuasive, since it is clear that for example knowing that $1+\frac{1}{2^2}+\frac{1}{n^2}\lt 2$ cannot by itself imply that $1+\frac{1}{2^2}+\frac{1}{n^2}+\frac{1}{(n+1)^2}\lt 2$
Best Answer
Here is the first example I saw of induction, and I still think it's a beautiful one.
Problem: Prove that a $2^n \times 2^n$ sheet of graph paper with one box removed, can be tiled with L-shaped trominos.
Proof: For the $n=1$ case, there is nothing to prove: a $2 \times 2$ grid with one box removed is exactly a L-tromino.
For $n=2$, consider the $4 \times 4$ grid. You can divide it into four $2\times 2$ grids. The removed box is in one of those four sub-grids, so that sub-grid can be covered with an L-tromino (is an L-tromino, rather). What about the other 3 sub-grids? Put an L-tromino right in the center of the huge grid, which covers them!
Now the remaining part of each of them is a $2\times2$ grid with one box removed. I leave it to you to complete the proof, and teach it to the students as you best see fit.
The figures above are from Mathematical Circles: Russian Experience by Dmitri Fomin, Sergey Genkin, and Ilia Itenberg, specifically the chapter on Induction which is written by I.S. Rubanov. The book actually doesn't use a variable $n$, but asks for a $16\times 16$ square, then in the form of a discussion between a teacher and a student works through the $2\times 2$ and $4\times 4$ and $8\times 8$ cases, until it is obvious that we have in fact proved a theorem for any $2^n \times 2^n$ ('It looks like we have a "wave of proofs running along the chain of theorems $2\times2 \longrightarrow 4\times4 \longrightarrow 8\times8 \longrightarrow$ It is quite evident that the wave will not miss any statement in this chain.')
As an aside, this is a lovely book with quite a bit of non-trivial mathematics suitable for elementary school and high-school students (though I read in late high school).
This theorem and proof are also on the cut-the-knot website: Tromino Puzzle and Golomb's Inductive Proof.