## Tuesday, April 11, 2006

### 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$.

#### 1 comment:

1. a similar problem was on IMO shortlist 98 (?), proposed by US i think!