Fibby Squares. Topic: NT/Sequences & Series. Level: Olympiad.

Problem: (360 Problems For Mathematical Contests - 2.1.54) Let $ (a_n)_{n \ge 0} $ be the sequence defined by $ a_0 = 0 $, $ a_1 = 1 $ and

$ \frac{a_{n+1}-3a_n+a_{n-1}}{2} = (-1)^n $

for all integers $ n > 0 $. Prove that $ a_n $ is a perfect square for all $ n \ge 0 $.

Solution: The condition doesn't give many clues, so we find a couple of values - we see that $ a_2 = 1 $, $ a_3 = 4 $, $ a_4 = 9 $, $ a_5 = 25 $, $ a_6 = 64 $, $ a_7 = 169 $. Taking the square roots, we have the sequence $ 0, 1, 1, 2, 3, 5, 8, 13 $ which looks suspiciously like the Fibonnaci Sequence.
We claim that $ a_n = F_n^2 $ for all $ n \ge 0 $ where $ F_0 = 0 $, $ F_1 = 1 $ and $ F_{n+1} = F_n+F_{n-1} $ for $ n > 0 $.

We will proceed by induction.

Base Case - $ a_0 = F_0^2 $, $ a_1 = F_1^2 $, $ a_2 = F_2^2 $

Induction Step - $ a_{n-2} = F_{n-2}^2 $, $ a_{n-1} = F_{n-1}^2 $, and $ a_n = F_n^2 $ imply that $ a_{n+1} = F_{n+1}^2 $

Consider the two relations

$ \frac{a_n-3a_{n-1}+a_{n-2}}{2} = (-1)^{n-1} $

$ \frac{a_{n+1}-3a_n+a_{n-1}}{2} = (-1)^n $.

Adding them up, we find that the RHS becomes zero, so

$ a_{n+1}-2a_n-2a_{n-1}+a_{n-2} = 0 $

$ a_{n+1} = 2a_n+2a_{n-1}-a_{n-2} $

By our inductive hypothesis, we may substitute to obtain

$ a_{n+1} = 2F_n^2+2F_{n-1}^2-F_{n-2}^2 $.

But recall that $ F_{n-2} = F_n-F_{n-1} $, so

$ a_{n+1} = 2F_n^2+2F_{n-1}^2-(F_n-F_{n-1})^2 $,

which simplifies to

$ a_{n+1} = F_n^2+F_{n-1}^2+2F_nF_{n-1} = (F_n+F_{n-1})^2 = F_{n+1}^2 $,

completing the induction. Hence we have $ a_n = F_n^2 $ for all $ n \ge 0 $, as claimed. QED.

--------------------

Comment: Looking for a pattern is often the way to go with these problems. Once you find one, you can try to prove it, but before you have something to prove you can't do much. The $ (-1)^n $ term was also rather annoying, and the addition of the equations allowed us to get rid of it. Lastly, induction is pretty much the simplest way to go, especially with the recursive definitions.

--------------------

Practice Problem: (360 Problems For Mathematical Contests - 2.1.57) Let $ a_0 = a_1 = 3 $ and $ a_{n+1} = 7a_n-a_{n-1} $ for $ n \ge 1 $. Prove that $ a_n-2 $ is a perfect square for all $ n \ge 1 $.