How to prove each element of the following sequence is a perfect square? Sequence $\{a_n\}$ satisfies the following formula:
$a_{n+2}=14a_{n+1}-a_n+12$,
and $a_1=1, a_2=1$.
It is easy to check that $a_3=25$ and $a_4=361$.
The question is how to prove each element of the sequence $\{a_n\}$ is a perfect square?
 A: I don't know a simpler way than breaking down the generating function: let $b_n=a_n+1$; then $b_{n+2}$ $= a_{n+2}+1$ $= 14a_{n+1}-a_n+12+1$ $=14(b_{n+1}-1)-(b_n-1)+13$ $= 14b_{n+1}-b_n$, so the recurrence relation for $b_n$ is homogeneous.  The characteristic equation is $x^2-14x+1=0$ with roots $7\pm4\sqrt{3}$, which are themselves the squares of $2\pm\sqrt{3}$; note that $(2+\sqrt{3})(2-\sqrt{3})=1$.  This isn't coincidence: if you look at the equation $c_{n+2}=4c_{n+1}-c_n$ (whose characteristic equation $x^2-4x+1=0$ has $2\pm\sqrt{3}$ for its roots) with initial conditions $c_1=-1$, $c_2=1$ you'll find that you have $a_n=c_n^2$.
This works because we have $c_n=x(2+\sqrt{3})^n+y(2-\sqrt{3})^n$, with $x=\frac12(3\sqrt{3}-5)$ and $y=-\frac12(3\sqrt{3}+5)$and so when we square $c_n$ we get a result of the form $x^2(2+\sqrt{3})^{2n}+y^2(2-\sqrt{3})^{2n}+xy\left((2+\sqrt{3})(2-\sqrt{3})\right)^n$ — but $xy$ is $-1$ and the last term in parenthesesis just $1$ for all $n$, so $c_n^2+1$ is of the form $sz^n+t\bar{z}^n$ (where $\bar{z}$ denotes the conjugate with respect to $\sqrt{3}$), and so it satisfies a second-degree homogeneous linear equation with integer coefficients — specifically, the equation for $b_n$.
The key here is that the (conjugate) roots of the equation have norm $1$ in $\mathbb{Q}(\sqrt{3})$, so the cross term will always be $1$; there's no exponential growth there, so we can offset the square by a constant factor to get another homogeneous linear equation.  The same trick would work for e.g. an equation like $x^2-66x+1=0$ (i.e., $c_{n+2}=66c_{n+1}-c_n$) with conjugate roots $z,\bar{z}=33\pm8\sqrt{17}$ that satisfy $z\bar{z}=1$; with the right initial conditions you'll find exactly the same phenomenon that the solutions of $d_{n+2}=4354d_{n+1}-d_n$ (whose roots are $z^2$ and $\bar{z}^2$) satisfy $d_n=c_n^2-1$.
A: As Umberto P. commented, it is sufficient to prove by induction that
$$a_{n+2}=b_n^2\tag1$$
where $b_{n+2}=4b_{n+1}-b_{n}$ with $b_0=1, b_1=5$.
The base case : $a_2=1=b_0^2$ and $a_3=25=b_1^2$
Suppose that $a_{n+2}=b_n^2$ and $a_{n+1}=b_{n-1}^2$. 
Then, using that 
$$b_n^2-4b_nb_{n-1}+b_{n-1}^2=6\tag2$$
we get
$$\begin{align}a_{n+3}&=14a_{n+2}-a_{n+1}+12\\&=14b_{n}^2-b_{n-1}^2+12\\&=16b_n^2-8b_nb_{n-1}+b_{n-1}^2-2b_n^2+8b_nb_{n-1}-2b_{n-1}^2+12\\&=(4b_n-b_{n-1})^2-2(b_n^2-4b_nb_{n-1}+b_{n-1}^2-6)\\&=b_{n+1}^2\qquad\blacksquare\end{align}$$

Let us prove $(2)$ by induction.
The base case : $b_1^2-4b_1b_0+b_0^2=25-20+1=6$
Suppose that $b_n^2-4b_nb_{n-1}+b_{n-1}^2=6$. Then,
$$\begin{align}b_{n+1}^2-4b_{n+1}b_{n}+b_{n}^2&=(4b_{n}-b_{n-1})^2-4(4b_{n}-b_{n-1})b_n+b_n^2\\&=16b_{n}^2-8b_{n}b_{n-1}+b_{n-1}^2-16b_n^2+4b_nb_{n-1}+b_n^2\\&=b_n^2-4b_nb_{n-1}+b_{n-1}^2\\&=6\qquad\blacksquare\end{align}$$
A: The above proofs are elegant. The following is what I was thinking:
Like what Steven did, we can use generation functions and write out $$a_n = c(2+\sqrt{3})^{2n} + d(2-\sqrt{3})^{2n} - 1$$ for some constants $c$ and $d$. Note that $c>0$ since $a_n$ increases as $n$ increases. If $d>0$, then $a_n = (\sqrt{c}((2+\sqrt{3})^n - \sqrt{d}(2-\sqrt{3})^n)^2 + (2\sqrt{cd} - 1 )$, and we want to show $ 2\sqrt{cd} - 1=0$, or $cd=1/4$.  
Write $\sigma = (2+\sqrt{3})$,  from $a_1=a_2$ we have $c\sigma^2 + d\sigma^{-2} = c\sigma^4 + d\sigma^{-4}$, which simplifies to $d=c\sigma^6$; then $d>c>0$.  We also have $2=a_1+1= c\sigma^2 + d\sigma^{-2} = c\sigma^2(1+\sigma^2) = c\sigma^2*4\sigma$, so $c\sigma^3= 1/2$, which yields $2\sqrt{cd} - 1= 2c\sigma^3-1= 0$. We then have $a_n=b_n^2$, where $b_n=\sqrt{c}(2+\sqrt{3})^n - \sqrt{d}(2-\sqrt{3})^n$. The sequence $\{b_n\}$ are integers since $b_1=b_2=1$ and $b_{n+2} = 4b_{n+1}-b_n$.  
