Source: 2002 UofT Math Competition, problem 9.
A sequence whose entries are 0 and 1 has the property that, if each 0 is replaced by 01 and each 1 by 001, the sequence remains unchanged. What is the 2002th term of the sequence?
Let $S_1 = 0$ and for $k\ge 2$ let $S_k$ be obtained from $S_{k-1}$ by replacing every 0 in $S_{k-1}$ with $01$ and every $1$ with $001$. The crucial claim is that $S_k = S_{k-1}S_{k-2}S_{k-1}$ for all $k\ge 3$.
I'm not sure if this can be shown using some form of induction.
The claim clearly justifies that the given sequence is well-defined, since $S_{k-1}$ is a prefix of $S_k$.
From the claim, the answer is easy: The length of the $S_k$'s for $1\leq k\leq 10$ are $1,2,5,12,29,70,169,408,985,2378.$ Let $S_{k,i}$ denote the ith symbol of $S_k$ where $i$ is at most the length of $S_k$. Then $S_{10,2002} = S_{9, 2002-985-408} = S_{9,609} = S_{8,609-408-169} = S_{8,32} = S_{7,32}=S_{6,32} = S_{4,32-29} = S_{3,3} = 0.$
As Greg Martin indicated, you can use induction to prove the crucial claim. When I have encountered this kind of claim and its proof for the first time, I was like, uh, so easy and obvious?!
Let $\phi$ map strings to strings by replacing each $0$ with $01$ and each $1$ by $001$.
It is straightforward to see that $\phi$ preserves string concatenation, i.e., $\phi(st)=\phi(s)\phi(t)$, where $s$ and $t$ are two arbitrary strings, $st$ is the concatenation of $s$ and $t$.
You have constructed $S_k$ by $S_{k+1}=\phi(S_k)$.
Suppose $S_k = S_{k-1}S_{k-2}S_{k-1}$. Then $$S_{k+1} = \phi(S_{k-1}S_{k-2}S_{k-1})=\phi(S_{k-1})\phi(S_{k-2})\phi(S_{k-1})=S_{k}S_{k-1}S_{k}$$
The base case is $S_3=01001=(01)0(01)=S_2S_1S_2$.