Problem 32: PEN, Linear Recurrences, Problem 13

by henderson, Jul 2, 2016, 11:21 AM

$\bf\color{red}Problem \ 32$ The sequence $\{x_n\}_{n\geq 1}$ is defined by
$x_1=x_2=1, x_{n+2}=14x_{n+1}-x_n-4.$ Prove that $x_n$ is always a perfect square.
$\bf\color{red}My \ solution$ $\color{green}\textbf{Claim.}$ $\begin{align*} &4\sqrt{x_{n+1}}-\sqrt{x_n}=\sqrt{x_{n+2}}\ (\bigstar) \end{align*}$ for all $n\in \mathbb{N}.$

$\color{green}\textbf{Proof.}$ We will prove this relation by induction.

For $n=1,$
$\begin{align*} &4\sqrt{x_{2}}-\sqrt{x_1}=\sqrt{x_{n+3}} \iff 4\sqrt{1}-\sqrt{1}=\sqrt{9}, \end{align*}$ which is obvious.
Now, let us assume that $(\bigstar)$ holds, and then prove it for $n+1.$ So, it suffices to prove the following equation:
$\begin{align*} &4\sqrt{x_{n+2}}-\sqrt{x_{n+1}}=\sqrt{x_{n+3}}.\ (\blacksquare) \end{align*}$

Since $4\sqrt{x_{n+1}}-\sqrt{x_n}=\sqrt{x_{n+2}},$ we conclude
$4\sqrt{x_{n+1}}=\sqrt{x_n}+\sqrt{x_{n+2}}$ $\Longrightarrow$
$16x_{n+1}=x_n+x_{n+2}+2\sqrt{x_n\cdot x_{n+2}}$ $\Longrightarrow$
$16x_{n+1}=14x_{n+1}-4+2\sqrt{x_n\cdot x_{n+2}}$ $\Longrightarrow$
$x_{n+1}+2=\sqrt{x_n\cdot x_{n+2}}$ $\Longrightarrow$
$\begin{align*} &x^2_{n+1}+4x_{n+1}+4=x_n\cdot x_{n+2}. \ (\clubsuit) \end{align*}$

Let's prove $(\blacksquare)$ using $(\clubsuit):$
$4\sqrt{x_{n+2}}-\sqrt{x_{n+1}}=\sqrt{x_{n+3}}$ $\iff$
$4\sqrt{x_{n+2}}=\sqrt{x_{n+1}}+\sqrt{x_{n+3}}$ $\iff$
$16x_{n+2}=x_{n+1}+x_{n+3}+2\sqrt{x_{n+1}\cdot x_{n+3}}$ $\iff$
$16x_{n+2}=14x_{n+2}-4+2\sqrt{x_{n+1}\cdot x_{n+3}}$ $\iff$
$x_{n+2}+2=\sqrt{x_{n+1}\cdot x_{n+3}}$ $\iff$
$\begin{align*} &x^2_{n+2}+4x_{n+2}+4=x_{n+1}\cdot x_{n+3} \end{align*}$ $\iff$
$x_{n+2}\cdot(x_{n+2}+4)+4=x_{n+1}\cdot x_{n+3}$ $\iff$
$x_{n+2}\cdot(14x_{n+1}-x_n)+4=x_{n+1}\cdot x_{n+3}$ $\iff$
$14x_{n+1}x_{n+2}-x_nx_{n+2}+4=x_{n+1}\cdot x_{n+3}$ $\iff$
$\begin{align*} &14x_{n+1}x_{n+2}-(x^2_{n+1}+4x_{n+1}+4)+4=x_{n+1}\cdot x_{n+3} \ (I \ used \ \clubsuit \ here) \end{align*}$ $\iff$
$14x_{n+1}x_{n+2}-x^2_{n+1}-4x_{n+1}=x_{n+1}\cdot x_{n+3}$ $14x_{n+2}-x_{n+1}-4=x_{n+3},$ which is clear because of the given condition
$x_{n+2}=14x_{n+1}-x_n-4$ for all $n\in \mathbb{N}.$

The last step: Since the first $2$ terms are perfect squares and there is a linear relationship between $3$ consecutive $\sqrt{x_i}$ -s, the conclusion follows. $\square$