Problem: A \emph{word} is defined as any finite string of letters.
A word is a \emph{palindrome} if it reads the same backwards and forwards.
Let a sequence of words $W_0$, $W_1$, $W_2$, \dots\ be defined as follows:
$W_0 = a$, $W_1 = b$, and for $n \ge 2$,
$W_n$ is the word formed by writing $W_{n-2}$ followed by $W_{n-1}$.
Prove that for any $n \ge 1$, the word formed by writing
$W_1$, $W_2$, $W_3$, \dots, $W_n$ in succession is a palindrome.

Solution: To aid in following the solution, here are the first several words:
\begin{align*}
  W_0 &= a \\
  W_1 &= b \\
  W_2 &= ab \\
  W_3 &= bab \\
  W_4 &= abbab \\
  W_5 &= bababbab \\
  W_6 &= abbabbababbab \\
  W_7 &= bababbababbabbababbab
\end{align*}
We prove that $W_1 W_2 \dots W_n$ is a palindrome by induction on $n$.
The base cases $n=1,2,3,4$ can be verified by hand.

For the inductive step, we let $\ol{X}$ denote the word $X$ written
backwards. Then
\begin{align*}
  W_1 W_2 \dots W_{n-3} W_{n-2} W_{n-1} W_n
  &\overset{\text{IH}}{=} (\ol{W_{n-1}} \ol{W_{n-2}} \ol{W_{n-3}}
    \dots \ol{W_2} \ol{W_1}) W_n \\
  &= (\ol{W_{n-1}} \ol{W_{n-2}} \ol{W_{n-3}}
    \dots \ol{W_2} \ol{W_1}) W_{n-2} W_{n-1} \\
  &= \ol{W_{n-1}} \ol{W_{n-2}} (\ol{W_{n-3}}
    \dots \ol{W_2} \ol{W_1}) W_{n-2} W_{n-1}
\end{align*}
with the first equality being by the induction hypothesis.
By induction hypothesis again the inner parenthesized term
is also a palindrome, and so this completes the proof.