Prove that every terms of a sequence defined by a recurrence relation is a perfect square.

I would be happy if you let me know how to tackle this problem. Thanks.

Solution 1:

Hint: You're on the right track. There does exist a linear recurrence relation for a sequence defined by some square roots of $a_n$, but not necessarily the positive ones (e.g. instead of $b_6=5$, you might have $b_6=-5$). Can you try to find a recurrence relation from there?

Solution 2:

The idea is to look for a linear recurrence relation among the square roots. Say we have a relation $b_n=c_1b_{n-1}+c_2b_{n-2}$. Assuming the roots of the characteristic polynomial are distinct, the general formula should be $b_n=d_1\lambda_1^n+d_2\lambda_2^n$ where $d_1,d_2$ are constants and $\lambda_1,\lambda_2$ are the roots of the characteristic polynomial. Then $b_n^2=d_1^2\left(\lambda_1^2\right)^n+d_2^2\left(\lambda_2^2\right)^n+2d_1d_2\left(\lambda_1\lambda_2\right)^n$, so it has a recurrence relation of order 3 where the product of two of the roots of the characteristic polynomial is the square of the third.

Now observe that 2 is a root of the characteristic polynomial (and you should observe this, because one thing to do when looking for the roots of a polynomial is apply the rational root theorem to look for rational roots). Also, the product of the other two roots is 4, which is $2^2$. This suggests that the square roots should satisfy a reucurrence relation with characteristic polynomial $\frac{x^3+x^2-2x-8}{x-2}$; this gives you the recurrence to test and it works, once you try sufficiently many combinations of positive and negative signs on the first two terms of the recurrence.