Proving the values obtained by a recurrence relation are always perfect squares? A problem appeared in a maths contest as follows: Consider a recurrence relation: $$a_{n+3}= - a_{n+2}+2a_{n+1}+ 8a_{n}$$ where the intial conditions are : $a_1=1;a_2=1;a_3=9$.
Then prove that the quantity $a_n$ is always a perfect square for any $n$. I tried to solve it using the characteristic equation method looking at the homogenous nature of it. But the roots were complex and it became near impossible to show by hand that the imaginary part would be zero and the real part would be a perfect square. Hence is there any way of without going through that route and getting a proof?
 A: This is a matter of choosing the signs of the square roots properly.  "Properly" here means that we want the square roots to satisfy a convenient recursion.  Playing around with the terms for a bit, we are led to the following:
We define the sequence $c_n$ recursively, by $$c_n=-c_{n-1}-2c_{n-2};\quad c_1=c_2=1.$$
We claim that $c_n^2=a_n$.
This is clear for $n=1,2,$ so it suffices to show that $b_n=(c_n)^2$ satisfies the recursion which defines the $a_n$.  We wish to show $$b_{n+3}=-b_{n+2}+2b_{n+1}+8b_n$$ and compute $$b_{n+3}=c_{n+3}^2=(c_{n+2}+2c_{n+1})^2=c_{n+2}^2+4c_{n+2}c_{n+1}+4c_{n+1}^2=b_{n+2}+4b_{n+1}+4c_{n+2}c_{n+1}$$  So we want to show $$b_{n+2}+4b_{n+1}+4c_{n+2}c_{n+1}=-b_{n+2}+2b_{n+1}+8b_n$$ 
$$\iff 2b_{n+2}+2b_{n+1}+4c_{n+2}c_{n+1}=8b_n$$
$$\iff 2(c_{n+1}+2c_n)^2 +2b_{n+1}+4c_{n+2}c_{n+1}=8b_n$$
$$\iff 2b_{n+1}+8b_n+8c_{n+1}c_n+2b_{n+1}+4c_{n+2}c_{n+1}=8b_n$$
$$\iff 4b_{n+1}=-4c_{n+1}\left(2c_n+c_{n+2}\right)$$
But $2c_n+c_{n+2}=-c_{n+1}$ by the defining recursion for the $c$s, so the right hand side is $4c_{n+1}^2=4b_{n+1}$, and we are done.
