¿Demostrando que los valores obtenidos por una relación de recurrencia son siempre cuadrados perfectos?

Question

Un problema que apareció en un concurso de matemáticas de la siguiente manera: Considere la posibilidad de una relación de recurrencia: $$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$.

Demostrar que la cantidad de $a_n$ es siempre un cuadrado perfecto para cualquier $n$. Traté de resolverlo utilizando la ecuación característica del método de mirar a la naturaleza homogénea de la misma. Pero las raíces son complejas y se hizo casi imposible de mostrar a través de la mano que la parte imaginaria sería cero y la parte real sería un cuadrado perfecto. Por tanto, ¿hay alguna manera de, sin pasar a través de esa ruta y conseguir una prueba?

Answer 1

Este es un asunto de la elección de los signos de las raíces cuadradas correctamente. "Correctamente" significa que queremos que las raíces cuadradas de satisfacer una conveniente recursividad. Jugando con los términos para un poco, que nos lleva a la siguiente:

Se define la secuencia de $c_n$ recursivamente, por $$c_n=-c_{n-1}-2c_{n-2};\quad c_1=c_2=1.$$

Pretendemos que $c_n^2=a_n$.

Esto es claro para $n=1,2,$ por lo que es suficiente para mostrar que $b_n=(c_n)^2$ satisface la recursividad, la cual define el $a_n$. Queremos mostrar $$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)$$

Pero $2c_n+c_{n+2}=-c_{n+1}$ por la definición de recursividad para la $c$s, por lo que el lado derecho es $4c_{n+1}^2=4b_{n+1}$, y hemos terminado.

Answer 2

ahora parecen tener los coeficientes correctos. Un enfoque es encontrar una recurrencia para las raíces cuadradas. No es una molestia que no sabemos si es un particular, $\sqrt d$ o $- \sqrt d$ que debe ser parte de esa secuencia. Sin embargo, una vez elegido, es el Número de Paredes técnica para probar si una secuencia satisface la recurrencia lineal.

Carl se acercó con $r_1=-1, r_2=-1, r_{n+2} = -r_{n+1} - 2r_n$

De hecho, si $$\color{blue}{ r_{n+2} = \alpha r_{n+1} + \beta r_n } , \; $$ entonces $$ \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} \; , $$ donde aquí tomamos $\alpha = \pm 1, \beta = -2 \; , \; \;$ y elegir las $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

Mientras tanto:

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