Acceso directo algebraico para encontrar$a^n + b ^n$?

Question

Recientemente, me encontré con este problema en línea:

Dado $a+b=1$$a^2+b^2=2$, encontramos a $a^7+b^7$.

Aunque me podría haber solucionado sustituyendo en la primera ecuación a la segunda y, a continuación, utilizando la fórmula cuadrática; la forma de la pregunta, yo sospechaba que había un acceso directo. Sin embargo, no podía encontrar la solución a ese problema en ese sitio web, por lo que yo estoy pidiendo aquí:

Si se le $a+b$$a^2+b^2$, hay un acceso directo a la búsqueda de $a^n+b^n$?

Answer 1

Tenga en cuenta que $$a^{n+1}+b^{n+1}=(a^n+b^n)(a+b)-ab(a^{n-1}+b^{n-1}).\tag{1}$$ Desde $(a+b)^2=1$, e $a^2+b^2=2$, $2ab=-1$ y, por tanto,$ab=-\frac{1}{2}$.

Se sigue de (1) que $$a^{n+1}+b^{n+1}=(a^n+b^n)(1)+\frac{1}{2}(a^{n-1}+b^{n-1}).$$

Deje $f(k)=a^k+b^k$. Hemos obtenido la recurrencia $$f(n+1)=f(n)+\frac{1}{2}f(n-1).$$ El uso de esta recurrencia, se puede calcular nuestro camino a $f(7)$ con bastante rapidez.

Observaciones: $1.$ La misma estrategia puede ser utilizado para cualquier $a+b$$a^2+b^2$.

$2.$ Ir un poco más rápido, podríamos utilizar $a^{n+2}+b^{n+2}=(a^n+b^n)(a^2+b^2)-a^2b^2(a^{n-2}+b^{n-2})$.

$3.$ Si estamos en una prisa, y $n$ no es pequeño, hay varios trucos para acelerar los cálculos. Por ejemplo $$a^{2k}+b^{2k}=(a^k+b^k)^2-2(ab)^k.$$ Así que podemos tomar "gigante", pasos.