Proving the values obtained by a recurrence relation are always perfect squares?

Question

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?

Answer 1

you now seem to have the coefficients correct. One approach is to find a recurrence for the square roots. There is an annoyance that we do not know whether it is a particular $\sqrt d$ or $- \sqrt d$ that should be part of that sequence. However, once chosen, there is the Number Walls technique to test whether a sequence satisfies a linear recurrence.

Carl came up with $r_1=-1, r_2=-1, r_{n+2} = -r_{n+1} - 2r_n$

Indeed, if $$\color{blue}{ r_{n+2} = \alpha r_{n+1} + \beta r_n } , \; $$ then $$ \color{blue}{ r^2_{n+3} = (\alpha^2 + \beta) r^2_{n+2} + (\beta^2 + \alpha^2 \beta ) r^2_{n+1} - \beta^3 r_n^2} \; , $$ where here we take $\alpha = \pm 1, \beta = -2 \; , \; \;$ and choose appropriate $r_1,r_2.$

jagy@phobeusjunior:~$ ./mse
1    -1 =   -1 *  1 
2    -1 =   -1 *  1 
3    3 =  3
4    -1 =   -1 *  1 
5    -5 =  -5
6    7 =  7
7    3 =  3
8    -17 =  -17
9    11 =  11
10    23 =  23
11    -45 =   -1 * 3^2 5
12    -1 =   -1 *  1 
13    91 =  7 13
14    -89 =  -89
15    -93 =   -1 * 3 31
16    271 =  271
17    -85 =   -1 * 5 17
18    -457 =  -457
19    627 =  3 11 19
20    287 =  7 41
21    -1541 =   -1 * 23 67
22    967 =  967
23    2115 =  3^2 5 47
24    -4049 =  -4049
25    -181 =  -181
26    8279 =  17 487
27    -7917 =   -1 * 3 7 13 29
28    -8641 =  -8641
29    24475 =  5^2 11 89
30    -7193 =  -7193
31    -41757 =   -1 * 3 31 449
32    56143 =  23 2441
33    27371 =  101 271
34    -139657 =   -1 * 7 71 281
35    84915 =  3^3 5 17 37

Meanwhile:

jagy@phobeusjunior:~$ ./mse
1    1 =   1 
2    1 =   1 
3    9 =  3^2
4    1 =   1   sqrt  1
5    25 =  5^2  sqrt  5
6    49 =  7^2  sqrt  7
7    9 =  3^2  sqrt  3
8    289 =  17^2  sqrt  17
9    121 =  11^2  sqrt  11
10    529 =  23^2  sqrt  23
11    2025 =  3^4 5^2  sqrt  45
12    1 =   1   sqrt  1
13    8281 =  7^2 13^2  sqrt  91
14    7921 =  89^2  sqrt  89
15    8649 =  3^2 31^2  sqrt  93
16    73441 =  271^2  sqrt  271
17    7225 =  5^2 17^2  sqrt  85
18    208849 =  457^2  sqrt  457
19    393129 =  3^2 11^2 19^2  sqrt  627
20    82369 =  7^2 41^2  sqrt  287
21    2374681 =  23^2 67^2  sqrt  1541
22    935089 =  967^2  sqrt  967
23    4473225 =  3^4 5^2 47^2  sqrt  2115
24    16394401 =  4049^2  sqrt  4049
25    32761 =  181^2  sqrt  181
26    68541841 =  17^2 487^2  sqrt  8279
27    62678889 =  3^2 7^2 13^2 29^2  sqrt  7917
28    74666881 =  8641^2  sqrt  8641
29    599025625 =  5^4 11^2 89^2  sqrt  24475
30    51739249 =  7193^2  sqrt  7193
31    1743647049 =  3^2 31^2 449^2  sqrt  41757
32    3152036449 =  23^2 2441^2  sqrt  56143
33    749171641 =  101^2 271^2  sqrt  27371
34    19504077649 =  7^2 71^2 281^2  sqrt  139657
35    7210557225 =  3^6 5^2 17^2 37^2  sqrt  84915

Answer 2

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.