2011 USAJMO Problems/Problem 4

Problem

A word is defined as any finite string of letters. A word is a palindrome if it reads the same backwards as 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$ , $\dots$ , $W_n$ in succession is a palindrome.

Solution

Let $r$ be the reflection function on the set of words, namely $r(a_1\dots a_n) = a_n \dots a_1$ for all words $a_1 \dots \a_n$ (Error compiling LaTeX. Unknown error_msg), $n\ge 1$ . Then the following property is evident (e.g. by mathematical induction):

$r(w_1 \dots w_k) = r(w_k) \dots r(w_1)$ , for any words $w_1, \dots, w_k$ , $k \ge 1$ .

a, b, ab, bab, We use mathematical induction to prove the statement of the problem. First, $W_1 = b$ , $W_1W_2 = bab$ , $W_3 = babbab$ are palindromes. Second, suppose $n\ge 3$ , and that the words $W_1 W_2 \dots W_k$ ( $k = 1$ , $2$ , $\dots$ , $n$ ) are all palindromes, i.e. $r(W_1W_2\dots W_k) = W_1W_2\dots W_k$ . Now, consider the word $W_1 W_2 \dots W_{n+1}$ :