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

Question

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

Matemáticas
pregunta suave
números de fibonacci
relaciones de recurrencia
secuencias y series
matemáticas-recreativas

Arte simplemente hermoso

Así que recientemente pensé en una forma genial de representar la secuencia de Fibonacci, que proporciona muchas identidades realmente interesantes. La clave es definir

X^{2} = X + 1

$x^2=x+1$

Y considere las secuencias enteras dadas por

X^{norte} = a_{norte} X + b_{norte}

$x^n=a_nx+b_n$

Estas secuencias satisfacen $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 comprobable:

\begin{aligned} a_{norte + 2} X + b_{norte + 2} & = X^{norte + 2} \\ = X^{norte} X^{2} \\ = X^{norte} (X + 1) \\ = X^{norte + 1} + X^{norte} \\ = a_{norte + 1} X + b_{norte + 1} + a_{norte} X + b_{norte} \\ = (a_{norte + 1} + a_{norte}) X + (b_{norte + 1} + b_{norte}) \end{aligned}

$\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 llegar a un simple $\mathcal O(\log(n))$ algoritmo para calcular $F_n$ usando exponenciación al cuadrado:

\begin{aligned} a_{2 norte} X + b_{2 norte} & = X^{2 norte} \\ = (X^{norte})^{2} \\ = (a_{norte} X + b_{norte})^{2} \\ = a_{norte}^{2} X^{2} + 2 a_{norte} b_{norte} X + b_{norte}^{2} \\ = a_{norte}^{2} (X + 1) + 2 a_{norte} b_{norte} X + b_{norte}^{2} \\ = a_{norte} (a_{norte} + 2 b_{norte}) X + a_{norte}^{2} + b_{norte}^{2} \end{aligned}

$\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 de manera similar para $x^{2n+1}$ . Esto también le da rápidamente otras identidades geniales usando el hecho de que $x^{n+k}=x^nx^k$ , Por ejemplo.

Estaba pensando, sin embargo, que esto es demasiado conveniente. No estoy seguro de cómo generalizar esto . Por ejemplo, ¿qué pasaría si quisiera comenzar con diferentes números enteros?

También tengo curiosidad por saber si hay algo más en esto. Algunas matemáticas más profundas detrás de escena que pueden explicar por qué puedo escribir la secuencia de Fibonacci de esta manera, aparte de solo la fuerza bruta que muestra que satisface la definición.

En lo que respecta a comenzar en diferentes números enteros, podemos considerar las secuencias dadas por

X^{norte} (a_{0} X + a_{1} - a_{0}) = a_{norte} X + b_{norte}

$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.

Por lo que sé, es posible hacer esto con cualquier relación de recurrencia de la forma

X_{norte + k} = y_{1} X_{norte + k - 1} + \dots + y_{k} X_{norte}

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

considerando el correspondiente

X^{k} = y_{1} X^{k - 1} + \dots + y_{k}

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

y considerando las sucesiones dadas por

X^{norte} PAG (X) = a_{norte} X + b_{norte}

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

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

Así que esto me deja la pregunta de si hay o no más matemáticas relevantes aquí aparte de que me topé con esto. Pregunto esto porque creo que este tipo de identidad es simplemente "demasiado bueno para ser verdad", especialmente para mí por no haber notado este tipo de cosas a pesar de haber visto muchas relaciones de recurrencia antes.

Respuestas (3)

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

Vasili Mitch · Answer 1

Has construido un campo de Fibonacci (?) $Q[x]/(x^2-x-1)$ . Cada elemento de este campo se puede escribir como binomial, por lo que tiene representación en matrices de 2x2:

a X + b \Leftrightarrow (\begin{matrix} a + b & a \\ a & b \end{matrix}) = a F + b I

$ax+b\qquad\Leftrightarrow\quad \begin{pmatrix}a+b & a\\ a & b\end{pmatrix} = aF+bI$ Puedes comprobar eso

F^{2} = {(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})}^{2} = F + I

$F^2=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix}^2=F+I$

Tú $O(\log n)$ El algoritmo es un método de duplicación bien conocido , que es esencialmente un algoritmo de multiplicación rápida para la matriz. $F$ .

Para generalizar, solo debe seleccionar el primer elemento derecho. Entonces, en fibonacci ordinario, comienzas 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$ etcétera. Si quieres empezar con (-1, 2), entonces $Y_1=-1x+2$ , $Y_2=x Y_1$ , $y_3=x^2 Y_1$ etcétera. 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

X y = α X^{3} + β X^{2} + γ X = (β + α) X^{2} + (γ + α) X + α

$xy = \alpha x^3+\beta x^2+\gamma x = (\beta+\alpha)x^2 + (\gamma+\alpha)x+\alpha$ Entonces elemento

x

$x$ es equivalente a matriz:

T = (\begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) .

$T = \begin{pmatrix}1 & 1& 1\\ 1 & 0&0\\0&1&0\end{pmatrix}.$ Entonces nuestro campo se puede representar con

Q [I, T]

$Q[I, T]$

+1 Me gusta la interpretación de la matriz. Normalmente lo veo como ${(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})}^{norte} = (\begin{matrix} F_{norte + 1} & F_{norte} \\ F_{norte} & F_{norte - 1} \end{matrix})$ $\begin{pmatrix}1&1\\1&0\end{pmatrix}^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}$ pero me hace dudar. ¿Su método de duplicación no requiere guardar 4 valores (o 3 valores, supongo) en cada paso, mientras que el mío solo requiere 2 valores? En general, todas mis identidades solo requieren 2 valores, $a_n$ y $b_n$ , mientras que pasar por el tuyo usa 4 valores, entonces, ¿son realmente lo mismo?
¿Cómo manejan sus matrices algo como $X^{metro norte} = (X^{metro})^{norte} = (F_{metro} X + F_{metro - 1})^{norte} = \sum_{k = 0}^{norte} (\binom{norte}{k}) F_{metro}^{k} F_{metro - 1}^{norte - k} X^{k} \Rightarrow F_{metro norte} = \sum_{k = 0}^{norte} (\binom{norte}{k}) F_{metro}^{k} F_{metro - 1}^{norte - k} F_{k}$ $x^{mn}=(x^m)^n=(F_mx+F_{m-1})^n=\sum_{k=0}^n\binom nkF_m^kF_{m-1}^{n-k}x^k\Rightarrow F_{mn}=\sum_{k=0}^n\binom nkF_m^kF_{m-1}^{n-k}F_k$ ? ¿ Viendo que la expansión binomial de la matriz falla en general ?
En cuanto al almacenamiento, tiene razón si desea mantener las matrices como están. Pero puede almacenar solo la primera fila (y calcular la segunda),
Las matrices son solo una representación estándar. Son absolutamente equivalentes a su campo polinomial. En todos tus cálculos puedes reemplazar $x$ con $F$ y todo se cumplirá. No hay problema porque $F$ y $I$ conmutar, que es de lo que se trata la respuesta en su enlace.
Ah, está bien, no le importan los coeficientes constantes. Y si trato de hacer ecuaciones en diferencias lineales de orden superior, ¿obtendré matrices que conmutan?
Lo siento si eso no fue claro. Considere, por ejemplo, $x^3=x^2+x+1$ y $x^n=a_nx^2+b_nx+c_n$ . ¿Cómo representarías esto con matrices?

lee mosher · 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})$ dónde $M$ es un $k \times k$ matriz. Por ejemplo, hay una solución explícita para $x_n$ expresado en términos de las raíces características de $M$ .

Ya sé cómo resolver ecuaciones en diferencias lineales usando las raíces características, pero esto no proporciona ninguna forma de formar identidades como pude hacerlo aquí.

Marty Cohen · Answer 3

Bien por usted en el descubrimiento de estos.

Como sospechabas, estos ya se conocen como polinomios de Fibonacci.

Aquí hay un lugar razonable para comenzar:

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

Porque no hay ninguno. Lo que encontraste no tiene nada que ver con los polinomios de Fibonacci

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

Arte simplemente hermoso

Respuestas (3)

Vasili Mitch

Arte simplemente hermoso

Arte simplemente hermoso

Vasili Mitch

Vasili Mitch

Arte simplemente hermoso

Arte simplemente hermoso

Vasili Mitch

Vasili Mitch

lee mosher

Arte simplemente hermoso

Marty Cohen

Arte simplemente hermoso

Vasili Mitch

Demostrando la aproximación de forma cerrada de la relación de recurrencia Xk=kXk−1Xk=kXk−1X_k=\frac{k}{X_{k-1}}

Verificar que el 2n2n2n-ésimo término en una sucesión de Fibonacci generalizada modificada de orden nnn es el n−1n−1n-1-ésimo número de Cullen

Recurrencia fn+2=afn+1+bfnfn+2=afn+1+bfnf_{n+2}=af_{n+1}+bf_n

Números de Fibonacci solución a esta relación de recurrencia

¿Nuevas identidades para los números de Fibonacci generalizados?

Una propiedad interesante de los números de Fibonacci

Número de series de Fibonacci que contienen un cierto número entero

Algunas series infinitas (¡solo por diversión!)

Números de Fibonacci y recurrencias lineales

¿Problemas recreativos en la teoría de conjuntos?