Don't Be Such A Square. Topic: NT/Sequences & Series. Level: Olympiad.

Problem: (Math Olympiad Treasures - 3.4.6) The sequence $ (a_n)_{n \ge 0 } $ is defined by $ a_0 = a_1 = 1 $ and

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

for all $ n \ge 1 $. Prove that the number $ 2a_n-1 $ is a square for all $ n \ge 0 $.

Solution: Define two new sequences $ (b_n)_{n \ge 0} $ by $ b_n = 2a_n-1 $ for $ n \ge 0 $ and $ (c_n)_{n \ge 0} $ by $ c_0 = -1, c_1 = 1 $ and $ c_{n+1} = 4c_n-c_{n-1} $ for $ n \ge 1 $. We claim that $ b_n = c_n^2 $ and since $ c_n $ is clearly a sequence of integers, this is the same as the desired result. Note that the recursion for $ b_n $ is $ b_{n+1} = 14b_n-b_{n+1}+12 $, which can be easily verified by substituting the $ b_n = 2a_n-1 $ back in.

First we will prove a lemma for the main proof. We claim that $ c_n^2+c_{n-1}^2 = 4c_nc_{n-1}+6 $ for all $ n \ge 1 $. We proceed by induction.

Base Case - $ c_1^2+c_0^2 = 4c_1c_0+6 \Leftrightarrow 1^2+(-1)^2 = 4(1)(-1)+6 \Leftrightarrow 2 = 2 $.

Induction Step - Suppose $ c_k^2+c_{k-1}^2 = 4c_kc_{k-1}+6 $. Then

$ c_{k+1}^2+c_k^2 = c_{k+1}^2+4c_kc_{k-1}-c_{k-1}^2+6 = c_{k+1}^2+c_{k-1}(4c_k-c_{k-1})+6 $.

Substituting $ c_{k+1} = 4c_k-c_{k-1} $ and $ c_{k-1} = 4c_k-c_{k+1} $, we have

$ c_{k+1}^2+c_k^2 = c_{k+1}^2+(4c_k-c_{k+1})c_{k+1}+6 $

$ c_{k+1}^2+c_k^2 = 4c_{k+1}c_k+6 $ (1),

completing the induction. Now we will use induction to prove that $ b_n = c_n^2 $ for $ n \ge 0 $.

Base Case - $ b_0 = c_0^2 \Leftrightarrow 1 = (-1)^2 \Leftrightarrow 1 = 1 $. $ b_1 = c_1^2 \Leftrightarrow 1 = 1^2 \Leftrightarrow 1 = 1 $.

Induction Step - Suppose $ b_k = c_k^2 $ and $ b_{k-1} = c_{k-1}^2 $. Then

$ b_{k+1} = 14b_k-b_{k-1}+12 = 14c_k^2-c_{k-1}^2+12 $.

Substituting $ c_{k-1} = 4c_k-c_{k+1} $ in, we have

$ b_{k+1} = 14c_k^2-(4c_k-c_{k+1})^2+12 $

$ b_{k+1} = 8c_{k+1}c_k-c_{k+1}^2-2c_k^2+12 $.

But from (1), we know $ c_{k+1}^2+c_k^2 = 4c_{k+1}c_k+6 \Rightarrow 8c_{k+1}c_k-c_{k+1}^2-2c_k^2+12 = c_{k+1}^2 $, so

$ b_{k+1} = c_{k+1}^2 $,

completing the induction. Hence we have shown that $ b_n = 2a_n-1 $ is always a square. QED.

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

Comment: This proof required quite a few steps to finish, notably the two different induction steps necessary to prove the desired result. The motive for defining $ c_n $ was as usual looking at the first few terms, which happen to be $ -1, 1, 5, 19, 71 $. This pretty much gives it away and then all that's left is the proof.

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

Practice Problem: (Math Olympiad Treasures - 3.4.5) Let $ x_1 = x_2 = 1, x_3 = 4 $ and

$ x_{n+3} = 2x_{n+2}+2x_{n+1}-x_n $

for all $ n \ge 1 $. Prove that $ x_n $ is a square for all $ n \ge 1 $.