We define the following sequence: $a_0=a_1=1$, $a_{n+1}=14a_n-a_{n-1}$. Prove that $2a_n-1$ is a perfect square.
Problem
Source: V International Festival of Young Mathematicians Sozopol 2014, Theme for 10-12 grade
Tags: number theory, Sequence
01.07.2020 11:39
First of all, we prove that all $a_{n}$ are natural for natural $n$ by strong induction. Base: $a_{2} > a_{1} = 1$. Assume that for some natural $n$ we got $a_{n} > a_{n - 1} > ... > a_{1} = 1$ then $ a_{n + 1} = 14 a_{n} - a_{n - 1} > 14 a_{n} - a_{n} = 13 a_{n} > a_{n} \geq 1$. Proved. So all $a_{n}$ are naturals and it is correct to extract the square root from $2a_{n} - 1$. Let's consider the following sequence $ (b_{n}) = \sqrt{2a_{n} - 1}$. Of course, all $b_{n}$ are positive. It is easy to see that two first numbers in this sequence are integers. If we prove that all numbers in this sequence are integers it would follows that $2a_{n} - 1$ is a perfect square for all natural $n$. Claim: $(b_{n + 1}^{2} + b_{n - 1}^{2} - 16b_{n}^{2})^{2} = (2b_{n + 1}b_{n - 1})^{2}$. Proof: Last equality can be transformed into $b_{n +1 }^{4} + b_{n - 1}^{4} + 256 b_{n}^{4} - 2 b_{n + 1}^{2} b_{n - 1}^{2} - 32 b_{n + 1}^{2} b_{n}^{2} - 32 b_{n - 1}^{2} b_{n}^{2} = 0$. Substituting $ b_{n + 1}^{2} = 2a_{n + 1} - 1 = 28 a_{n} - 2 a_{n - 1} - 1$, $b_{n}^{2} = 2a_{n} - 1$ and $b_{n - 1}^{2} = 2a_{n - 1} - 1$ also opening the brackets and reducing similar terms we got $$a_{n}^{2} + a_{n - 1}^{2} - 14 a_{n} a_{n - 1} + 12 = 0 \leqno (1)$$ We will prove that (1) is true inductively. For $n = 1$ we got $1 + 1 - 14 + 12 = 0$ and it is true. Now it is easy to see that $a_{n}^{2} + a_{n - 1}^{2} - 14 a_{n} a_{n - 1} + 12 = 0 \Leftrightarrow 196 a_{n}^{2} + a_{n - 1}^{2} - 28 a_{n} a_{n - 1} + a_{n}^{2} - 196 a_{n}^{2} + 14 a_{n} a_{n - 1} + 12 = 0.$ But last equality can be transformed into $ (14 a_{n} - a_{n - 1})^{2} + a_{n}^{2} - 14(14 a_{n} - a_{n - 1}) a_{n} + 12 = a_{n + 1}^{2} + a_{n}^{2} - 14 a_{n + 1} a_{n} + 12 = 0$ So (1) is true for every natural $n$. So claim is also true. Now it is easy to notice that claim means that $b_{n + 1}^{2} + b_{n - 1}^{2} - 16b_{n}^{2} = 2b_{n + 1}b_{n - 1} $ or $b_{n + 1}^{2} + b_{n - 1}^{2} - 16b_{n}^{2} = - 2b_{n + 1}b_{n - 1} $. In the first case we got $(b_{n + 1} - b_{n - 1})^{2} = (4 b_{n})^{2}$. So $b_{n + 1} - b_{n - 1} = 4 b_{n}$ or $b_{n + 1} - b_{n - 1} = - 4 b_{n}$. But anyway we got that if $b_{n}$ and $b_{n - 1}$ are integers then $b_{n + 1}$ is integer too. In the second case we got $(b_{n + 1} + b_{n - 1})^{2} = (4 b_{n})^{2}$. So $b_{n + 1} + b_{n - 1} = 4 b_{n}$ or $b_{n + 1} + b_{n - 1} = - 4 b_{n}$. But we got again that if $b_{n}$ and $b_{n - 1}$ are integers then $b_{n + 1}$ is integer too. Since $b_{1}$ and $b_{2}$ are integers we got that all $(b_{n})$ are integers and we are done.
01.07.2020 11:50
The recurrence \[a_n^2+a_{n-1}^2-14a_na_{n-1}=-12\](from which everything immediately follows) can also be easily proved by Vieta: By induction. The quadratic equation \[x^2-14a_nx+a_n^2+12=0\]has the solution $x=a_{n-1}$, so by Vieta it has the second solution $x=14a_n-a_{n-1}$ which is just $a_{n+1}$.
01.07.2020 11:58
An alternative finish from this identity: So \[(a_{n+1}-7a_n)^2=48a_n^2-12=12 \cdot (2a_{n-1}-1)(2a_{n-1}+1).\]Hence $3(2a_n-1)(2a_n+1)$ is a perfect square for all $n$. But it is easy to prove by induction that $a_n \equiv 1 \mod 3$ so that this immediately implies that $2a_n-1$ is a perfect square.