Peter wrote: The sequence $\{x_{n}\}_{n \ge 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. Let's look at the suquence $y_{n}$ of positive integers,which is defined by $y_{1}=y_{2}=1$ and $y_{n+1}=4y_{n}-y_{n-1}$. We have that $y_{n+1}^{2}=16y_{n}^{2}+y_{n-1}^{2}-8y_{n}y_{n-1}$ and also $y_{n-1}^{2}=16y_{n}^{2}+y_{n+1}^{2}-8y_{n}y_{n+1}$. From latter follows that $8y_{n}y_{n+1}=16y_{n}^{2}+y_{n+1}^{2}-y_{n-1}^{2}$ therefore we also have that $8y_{n-1}y_{n}=16y_{n-1}^{2}+y_{n}^{2}-y_{n-2}^{2}$. We have proved that $y_{n+1}^{2}=16y_{n}^{2}+y_{n-1}^{2}-8y_{n}y_{n-1}$.Therefore, \[y_{n+1}^{2}=16y_{n}^{2}+y_{n-1}^{2}-(16y_{n-1}^{2}+y_{n}^{2}-y_{n-2}^{2})=15y_{n}^{2}-15y_{n-1}^{2}+y_{n-2}^{2}\] $\Longrightarrow$ \[y_{n+1}^{2}=15y_{n}^{2}-15y_{n-1}^{2}+y_{n-2}^{2}\] Now let's return to our initial sequence. $x_{n+2}= 14x_{n+1}-x_{n}-4$ $\Rightarrow$ $x_{n+1}=14x_{n}-x_{n-1}-4$ $\Rightarrow$ $x_{n+2}-x_{n+1}=14x_{n+1}-15x_{n}+x_{n-1}$ $\Leftrightarrow$ $x_{n+2}=15_{n+1}-15x_{n}+x_{n-1}$ $\Rightarrow$ \[x_{n+1}=15x_{n}-15x_{n-1}+x_{n-2}\] We have that $x_{1}=y_{1}^{2},x_{2}=y_{2}^{2}$ and $x_{3}=y_{3}^{2}$ $\Rightarrow$ $x_{n}=y_{n}^{2}$,as the problem clamed.

Peter wrote: The sequence $ \{x_{n}\}_{n\ge 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. The above proof by Tiks offers a natural generalization. Indeed, using the same method, one may establish the following result. Theorem Let $ u$, $ v$ and $ \lambda$ be given integers. Suppose that the sequence $ \{x_{n}\}_{n\ge 1}$ satisfies the recurrence relation \[ x_{n+2}=\left({\lambda}^{2}-2\right) x_{n+1}-x_{n}+2( u^{2}-\lambda uv+v^{2}),\;\; n\in\mathbb{N}\] and has the initial condition $ x_{1}= u^{2}$ and $ x_{2}= v^{2}$. Then, $ x_{n}$ is the square of an integer for all $ n\in\mathbb{N}$. Proof First, we need the following lemma. Lemma The sequence $ \{x_{n}\}_{n\ge 1}$ satisfies the following recurrence relation \[ x_{n+3}=\left({\lambda}^{2}-1\right) x_{n+2}-\left({\lambda}^{2}-1\right) x_{n+1}+x_{n},\;\; n\in\mathbb{N}.\] Proof of Lemma The original recurrence relation says that \[ x_{n+2}=\left({\lambda}^{2}-2\right) x_{n+1}-x_{n}+2( u^{2}-\lambda uv+v^{2}).\] Replace $ n$ by $ n+1$ in the equation to obtain \[ x_{n+3}=\left({\lambda}^{2}-2\right) x_{n+2}-x_{n+1}+2( u^{2}-\lambda uv+v^{2}).\] Subtracting the first equation from the second equation, we get the result. Now, we prove the main result. The main idea is to introduce a sequence $ \{y_{n}\}_{n\ge 1}$ of integers satisfying $ x_{n}={y_{n}}^{2}$ for all $ n\in\mathbb{N}$. Take the sequence $ \{y_{n}\}_{n\ge 1}$ by the recurrence relation \[ y_{n+2}=\lambda y_{n+1}-y_{n},\;\; n\in\mathbb{N}\] and impose the initial condition $ y_{1}= u$ and $ y_{2}= v$. It's clear that $ y_{n}$ is an integer for all $ n\in\mathbb{N}$. Our job is to establish that \[ x_{n}={y_{n}}^{2}\] for all $ n\in\mathbb{N}$. By its initial condition, it clearly holds for $ n = 1$ and $ 2$. It's an easy job to check the case of $ n = 3$. Indeed, we have \[ x_{3}=\left({\lambda}^{2}-2\right) x_{2}-x_{1}+2( u^{2}-\lambda uv+v^{2})=\left(\lambda v-u\right)^{2}={y_{3}}^{2}.\] If we prove that $ {y_{n}}^{2}$ satisfies the same recurrence relation in the lemma, we can complete the proof of $ x_{n}={y_{n}}^{2}$ by the induction on $ n$. So, we need to establish that \[ {y_{n+3}}^{2}=\left({\lambda}^{2}-1\right){y_{n+2}}^{2}-\left({\lambda}^{2}-1\right){y_{n+1}}^{2}+{y_{n}}^{2}\] for all $ n\in\mathbb{N}$. Step 1 We have \[ {y_{n+3}}^{2}={\lambda}^{2}{y_{n+2}}^{2}+{y_{n+1}}^{2}-2\lambda y_{n+2}y_{n+1}.\] Proof By squaring both sides of $ y_{n+2}=\lambda y_{n+1}-y_{n}$, we get \[ {y_{n+2}}^{2}={\lambda}^{2}{y_{n+1}}^{2}+{y_{n}}^{2}-2\lambda y_{n+1}y_{n}.\] Replacing $ n$ by $ n+1$ in the above equation, we get the result. Step 2 We have \[ {y_{n}}^{2}={\lambda}^{2}{y_{n+1}}^{2}+{y_{n+2}}^{2}-2\lambda y_{n+1}y_{n+2}.\] Proof From the recurrence relation, $ y_{n}=\lambda y_{n+1}-y_{n+2}$. By squaring both sides, we get \[ {y_{n}}^{2}={\lambda}^{2}{y_{n+1}}^{2}+{y_{n+2}}^{2}-2\lambda y_{n+1}y_{n+2}.\] Now, subtract the equation in the step $ 2$ from the equation in the step $ 1$ to obtain \[ {y_{n+3}}^{2}-{y_{n}}^{2}=\left({\lambda}^{2}-1\right){y_{n+2}}^{2}-\left({\lambda}^{2}-1\right){y_{n+1}}^{2}\] or \[ {y_{n+3}}^{2}=\left({\lambda}^{2}-1\right){y_{n+2}}^{2}-\left({\lambda}^{2}-1\right){y_{n+1}}^{2}+{y_{n}}^{2},\] as desired. I'm still hungry. We need to generalize it more. First, we look at the particular cases of the above result. Taking $ u = v = 1$ and $ \lambda = 4$ in the theorem, we obtain the problem L13. Taking $ u = v = 1$ in the theorem, we get the following result. Corollary Let $ \lambda$ be a given integer. Suppose that the sequence $ \{x_{n}\}_{n\ge 1}$ satisfies the recurrence relation \[ x_{n+2}=\left({\lambda}^{2}-2\right) x_{n+1}-x_{n}+2( 2-\lambda ),\;\; n\in\mathbb{N}\] and has the initial condition $ x_{1}= x_{2}= 1$. Then, $ x_{n}$ is the square of an integer for all $ n\in\mathbb{N}$. We recall the problem L10: (Bulgaria 2003) The sequence $ \{y_{n}\}_{n\ge 1}$ is defined by \[ y_{1}=y_{2}=1,\;\; y_{n+2}=(4k-5)y_{n+1}-y_{n}+4-2k.\] Determine all integers $ k$ such that each term of this sequence is a perfect square. One more similar problem comes from Vietnam 1998: Let $ a$ and $ b$ be integers. Define a sequence $ \{a_{n}\}_{n\ge 0}$ is defined by \[ a_{0}=a, a_{1}=b, a_{2}=2b-a+2,\;\; a_{n+3}=3a_{n+2}-3a_{n+1}+a_{n}.\] (a) Find the general term of the sequence. (b) Determine all $ a$, $ b$ for which $ a_{n}$ is a perfect square for all $ n\geq 1998$. Answer (a) $ a_{n}= n^{2}+(b-a-1)n+a$, (b) $ 4a = (b-a-1)^{2}$. Is there a super-generalization?

Peter wrote: The sequence $ \{x_{n}\}_{n\ge 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. $ y_{1}=y_{2}=1, y_{n+2}=4y_{n+1}-y_{n}$, a sequence of integers, satisfies $ x_{n}=y_{n}^{2}$. The reason for this (easy to prove why) is that $ (x^{2}-4x+1)(x^{2}+4x+1)=x^{4}-14x^{2}+1$

Sorry, I posted before I read through all of Hojoo's post... and I just wanted to comment that I unintentionally came up with the exact same generalization as his, but with different proof. I think my proof is much shorter, but more labor intensive (haha) We shift $ x_{n}$ by a constant so that the number drops out (in this case, it was $ 1/3$). We read off the characteristic polynomial and come up with the general term. We shift back by the constant. Now we substitute $ x^{2}$ for $ x$ in the characteristic poly, a factor it by difference of squares (see factorization in previous post). We take the resulting quadratic with real roots and make that our new magic sequence $ y_{n}$, and by design (and proper initial conditions) when we square the $ y_{n}$ general term the only thing that has to happen to complete our proof is to show that the shift we induced originally is equal to the "middle terms" from squaring, which is a constant. There are some uber generalizations to this thats for sure.

Peter wrote: The sequence $\{x_{n}\}_{n \ge 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{blue}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_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}\]$\iff$ \[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 relation between $3$ consecutive $\sqrt{x_i}$-s, the conclusion follows. $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \square$

Here's a closely related problem: Romania TST 2002