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 W0​,W1​,W2​,… be defined as follows: W0​=a,W1​=b, and for n≥2,Wn​ is the word formed by writing Wn−2​ followed by Wn−1​. Prove that for any n≥1, the word formed by writing W1​,W2​,…,Wn​ in succession is a palindrome.
Solution:
According to the statement of the problem we have
W0​=a,W1​=b,W2​=ab,W3​=bab,W4​=abbab
and so forth. Let Vn​=W1​W2​⋯Wn​, where we place two or more words next to one another to denote the single word obtained by writing all their letters in succession. We find that
V1​=b,V2​=bab,V3​=babbab,V4​=babbababbab
We wish to show that Vn​ is a palindrome for all positive integers n. The above list shows this to be true for 1≤n≤4; these cases will serve as the base cases for a proof by strong induction.
We use a bar over a word to indicate writing its letters in the reverse order. Thus W4​​= babba and V3​​=V3​ since V3​ is a palindrome. Now assume that the words V1​ through Vn​ are all palindromes; we will show that Vn+1​ is also a palindrome. By the definition of Vn+1​ and Wn+1​ we have
Vn+1​=Vn​Wn+1​=Vn​​Wn−1​Wn​
using the fact that Vn​​=Vn​ since Vn​ is a palindrome. But we know that Vn​=Vn−2​Wn−1​Wn​, so we may write
Vn​​Wn−1​Wn​=Wn​​Wn−1​​Vn−2​​Wn−1​Wn​
The latter word is clearly a palindrome since Vn−2​ reads the same forward as backwards. Hence Vn+1​ is a palindrome, thus completing the proof.
The problems on this page are the property of the MAA's American Mathematics Competitions