¿Hay algo más en esta relación con los números de Fibonacci?

Question

Así que hace poco se me ocurrió una forma genial de representar la secuencia de Fibonacci, que proporciona muchas identidades de forma realmente interesante. La clave es definir

$$x^2=x+1$$

Y consideremos las secuencias enteras dadas por

$$x^n=a_nx+b_n$$

Estas secuencias cumplen $F_{n+2}=F_{n+1}+F_n$ y $a_1=a_2=b_2=b_3=1$ produciendo así la sucesión de Fibonacci. Esto es fácilmente verificable:

\begin{align}\color{blue}{a_{n+2}}x+\color{green}{b_{n+2}}&=x^{n+2}\\&=x^nx^2\\&=x^n(x+1)\\&=x^{n+1}+x^n\\&=a_{n+1}x+b_{n+1}+a_nx+b_n\\&=(\color{blue}{a_{n+1}+a_n})x+(\color{green}{b_{n+1}+b_n})\end{align}

También se puede idear una sencilla $\mathcal O(\log(n))$ algoritmo para calcular $F_n$ utilizando la exponenciación al cuadrado:

\begin{align}\color{blue}{a_{2n}}x+\color{green}{b_{2n}}&=x^{2n}\\&=(x^n)^2\\&=(a_nx+b_n)^2\\&=a_n^2x^2+2a_nb_nx+b_n^2\\&=a_n^2(x+1)+2a_nb_nx+b_n^2\\&=\color{blue}{a_n(a_n+2b_n)}x+\color{green}{a_n^2+b_n^2}\end{align}

Y lo mismo para $x^{2n+1}$ . Esto también da rápidamente algunas otras identidades fresco utilizando el hecho de que $x^{n+k}=x^nx^k$ por ejemplo.

---

Sin embargo, estaba pensando que esto es demasiado conveniente. No sé cómo generalizar esto . Por ejemplo, ¿qué pasaría si quisiera empezar en números enteros diferentes?

También tengo curiosidad por saber si hay algo más. Alguna matemática más profunda entre bastidores que pueda explicar por qué soy capaz de escribir la secuencia de Fibonacci así, aparte de simplemente demostrar por fuerza bruta que satisface la definición.

---

En cuanto a empezar en números enteros diferentes, podemos considerar las secuencias dadas por

$$x^n(a_0x+a_1-a_0)=a_nx+b_n$$

que preserva la relación de recurrencia y nos permite elegir lo que queremos $a_0$ y $a_1$ ser.

Hasta donde yo sé, es posible hacer esto con cualquier relación de recurrencia de la forma

$$x_{n+k}=y_1x_{n+k-1}+\dots+y_kx_n$$

considerando la correspondiente

$$x^k=y_1x^{k-1}+\dots+y_k$$

y considerando las secuencias dadas por

$$x^nP(x)=a_nx+b_n$$

para algún polinomio $P$ que corresponde a las condiciones iniciales, siempre que $x$ es irracional para garantizar la unicidad.

Así que me queda la duda de si hay o no más matemáticas relevantes aquí aparte de mi simple tropiezo con esto. Pregunto esto porque creo que este tipo de identidad es "demasiado buena para ser verdad", especialmente para mí no haber notado este tipo de cosas a pesar de haber visto un montón de relaciones de recurrencia antes.

Answer 1

Has construido un campo Fibonacci (?) $Q[x]/(x^2-x-1)$ . Cada elemento de este campo se puede escribir como binomio, por lo que tiene representación en matrices de 2x2: $$ ax+b\qquad\Leftrightarrow\quad \begin{pmatrix}a+b & a\\ a & b\end{pmatrix} = aF+bI $$ Puede comprobar que $F^2=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix}^2=F+I $

Usted $O(\log n)$ es un conocido algoritmo el método de duplicación que es esencialmente un algoritmo de multiplicación rápida de matrices $F$ .

Para generalizar, sólo debe seleccionar el primer elemento correcto. Así que en fibonacci ordinario, se empieza con (1,0), que es $X_1=1x+0$ El siguiente elemento es $X_2=x X_1$ entonces $X_3=x^2 X_1$ y así sucesivamente. Si quieres empezar con (-1, 2), entonces $Y_1=-1x+2$ , $Y_2=x Y_1$ , $y_3=x^2 Y_1$ etc. Puedes usar el mismo algoritmo de multiplicación rápida para encontrar $Y_n$ .

Editar. Como ejemplo, quiero mostrar cómo construir un campo tribonacci $Q[x]/(x^3-x^2-x-1)$ .

Si tenemos $y=\alpha x^2+\beta x+\gamma$ entonces $$xy = \alpha x^3+\beta x^2+\gamma x = (\beta+\alpha)x^2 + (\gamma+\alpha)x+\alpha$$ Elemento $x$ es equivalente a matriz: $$ T = \begin{pmatrix}1 & 1& 1\\ 1 & 0&0\\0&1&0\end{pmatrix}. $$ Así que nuestro campo se puede representar con $Q[I, T]$

Answer 2

Existe una hermosa teoría general de ecuaciones en diferencias lineales es decir, recursiones de la forma $x_n = M(x_{n-1},...,x_{n-k})$ donde $M$ es un $k \times k$ matriz. Por ejemplo, existe una solución explícita para $x_n$ expresada en términos de las raíces características de $M$ .

Answer 3

Me alegro de que los hayas descubierto.

Como sospechaba, ya se conocen como polinomios de Fibonacci.

He aquí un punto de partida razonable:

https://en.wikipedia.org/wiki/Fibonacci_polynomials