Fórmula de de Moivre & Binet (n-ésimo término de la sucesión de Fibonacci)

Para discutir problemas de competencias para graduados de secundaria (Número de Oro, CIMA/Paenza, etcétera) y problemas que requieran conocimientos avanzados.
Avatar de Usuario
Yanes

OFO - Medalla de Bronce-OFO 2020 COFFEE - Mención-COFFEE Carolina González
Mensajes: 27
Registrado: Lun 05 Nov, 2018 8:59 pm
Medallas: 2
Nivel: Exolímpico

Fórmula de de Moivre & Binet (n-ésimo término de la sucesión de Fibonacci)

Mensaje sin leer por Yanes »

Sea $F:\mathbb{N}_0\to \text{Im}\in \mathbb{N}_0~/~F_n+F_{n+1}=F_{n+2},~F_0=0,~F_1=1$

$\Rightarrow F_n=\frac{\varphi ^n-(-\varphi )^{-n}}{2\varphi -1} $

Demostración:
Spoiler: mostrar
Tomamos a la definición de $F$:

$F_n+F_{n+1}=F_{n+2}$

$F_n+F_{n+1}-F_{n+2}=0$ (1)

Recordamos la definición de la Transformada $Z$ Unilateral:

$Z\left \{a_n\right \}=\sum \limits _{k=0}^{\infty}\frac{a_k}{z^k}$ (2)

Aplicamos (2) en (1):

$F_n+F_{n+1}-F_{n+2}=0$

$Z\left \{F_n+F_{n+1}-F_{n+2}\right \}=Z\{0\}$

$\sum \limits _{k=0}^{\infty}\frac{F_n+F_{n+1}-F_{n+2}}{z^k}=\sum \limits _{k=0}^{\infty}\frac{0}{z^k}$

Para evitar indeterminaciones en el segundo miembro: $z\neq 0$

$\sum \limits _{k=0}^{\infty}\frac{F_n}{z^k}+\sum \limits _{k=0}^{\infty}\frac{F_{n+1}}{z^k}-\sum \limits _{k=0}^{\infty}\frac{F_{n+2}}{z^k}=\sum \limits _{k=0}^{\infty}0$ (3)

Recordamos una propiedad de las sumatorias:

$\sum \limits _{k=m}^{n}a_{k+r}=\sum \limits _{k=m+r}^{n+r}a_k$ (4)

Aplicamos (4) en (3):

$\sum \limits _{k=0}^{\infty}\frac{F_n}{z^k}+\sum \limits _{k=0}^{\infty}\frac{F_{n+1}}{z^k}-\sum \limits _{k=0}^{\infty}\frac{F_{n+2}}{z^k}=\sum \limits _{k=0}^{\infty}0$

$\sum \limits _{k=0}^{\infty}\frac{F_n}{z^k}+\sum \limits _{k=0}^{\infty}\frac{F_{n+1}}{z^{k-1+1}}-\sum \limits _{k=0}^{\infty}\frac{F_{n+2}}{z^{k-2+2}}=0$

$\sum \limits _{k=0}^{\infty}\frac{F_n}{z^k}+\sum \limits _{k=0+1}^{\infty +1}\frac{F_{n}}{z^{k-1}}-\sum \limits _{k=0+2}^{\infty +2}\frac{F_{n}}{z^{k-2}}=0$

$\sum \limits _{k=0}^{\infty}\frac{F_n}{z^k}+\sum \limits _{k=1}^{\infty}\frac{F_n}{z^kz^{-1}}-\sum \limits _{k=2}^{\infty}\frac{F_n}{z^kz^{-2}}=0$

$\sum \limits _{k=0}^{\infty}\frac{F_n}{z^k}+\frac{1}{z^{-1}}\sum \limits _{k=1}^{\infty}\frac{F_n}{z^k}-\frac{1}{z^{-2}}\sum \limits _{k=2}^{\infty}\frac{F_n}{z^k}=0$

$\sum \limits _{k=0}^{\infty}\frac{F_n}{z^k}+z\left (\sum \limits _{k=1}^{\infty}\frac{F_n}{z^k}+\frac{F_0}{z^0}-\frac{F_0}{z^0}\right )-z^2\left (\sum \limits _{k=2}^{\infty}\frac{F_n}{z^k}+\frac{F_0}{z^0}+\frac{F_1}{z^1}-\frac{F_0}{z^0}-\frac{F_1}{z^1}\right )=0$

$\sum \limits _{k=0}^{\infty}\frac{F_n}{z^k}+z\left (\sum \limits _{k=0}^{\infty}\frac{F_n}{z^k}-\frac{F_0}{z^0}\right )-z^2\left (\sum \limits _{k=0}^{\infty}\frac{F_n}{z^k}-\frac{F_0}{z^0}-\frac{F_1}{z^1}\right )=0$

Recordamos que: $F_0=0,~F_1=1$ y $Z\left \{F_n\right \}=\sum \limits _{k=0}^{\infty}\frac{F_k}{z^k}$

$Z\left \{F_n\right \}+z\left (Z\left \{F_n\right \}-\frac{0}{z^0}\right )-z^2\left (Z\left \{F_n\right \}-\frac{0}{z^0}-\frac{1}{z^1}\right )=0$

$Z\left \{F_n\right \}+z\left (Z\left \{F_n\right \}\right )-z^2\left (Z\left \{F_n\right \}-\frac{1}{z}\right )=0$

$Z\left \{F_n\right \}+zZ\left \{F_n\right \}-z^2Z\left \{F_n\right \}-z^2\frac{1}{z}=0$

$Z\left \{F_n\right \}\left (1+z-z^2\right )-z=0$

$Z\left \{F_n\right \}\left (1+z-z^2\right )=z$

$\frac{Z\left \{F_n\right \}}{z}=\frac{1}{1+z-z^2}$

Separamos el segundo miembro con fracciones parciales:
Spoiler: mostrar
Factorizamos el polinomio $-z^2+z+1$ a $\left (z-z_1\right )\left (z-z_2\right )$

$z_{1,2}=\frac{-1\pm \sqrt{1^2-4(-1)(1)}}{2(-1)}$

$z_{1,2}=\frac{-1\pm \sqrt{1+4}}{-2}$

$z_{1,2}=\frac{1\pm \sqrt{5}}{2}$

$z_1=\frac{1+\sqrt{5}}{2}=\varphi$

$z_2=\frac{1-\sqrt{5}}{2}=\frac{2-1-\sqrt{5}}{2}=\frac{2}{2}+\frac{-1-\sqrt{5}}{2}=1-\frac{1+\sqrt{5}}{2}=1-\varphi$

Pero $1-\varphi =-\varphi ^{-1}$
Spoiler: mostrar

$\varphi$ es solución de $-z^2+z+1=0$

$-\varphi ^2+\varphi +1=0$

$\varphi -\varphi ^2=-1$

$\frac{\varphi -\varphi ^2}{\varphi}=\frac{-1}{\varphi}$

$\frac{\varphi}{\varphi}-\frac{\varphi ^2}{\varphi}=-\frac{1}{\varphi}$

$1-\varphi =-\varphi ^{-1}$
$z_2=1-\varphi =-\varphi ^{-1}$

$-z^2+z+1=\left (z-z_1\right )\left (z-z_2\right )$

$-z^2+z+1=\left (z-\varphi \right )\left (z-\left (-\varphi ^{-1}\right )\right )$

$-z^2+z+1=\left (z-\varphi \right )\left (z+\varphi ^{-1}\right )$

$\Rightarrow \frac{1}{1+z-z^2}=\frac{a}{z-\varphi}+\frac{b}{z+\varphi ^{-1}}$

$\Rightarrow a=\frac{1}{2\varphi -1},~b=-\frac{1}{2\varphi -1}$
Spoiler: mostrar
$\frac{a}{z-\varphi}+\frac{b}{z+\varphi ^{-1}}=\frac{a\left (z+\varphi ^{-1}\right )+b\left (z-\varphi \right )}{\left (z-\varphi \right )\left (z+\varphi ^{-1}\right )}=\frac{az+a\varphi ^{-1}+bz-b\varphi}{-z^2+z+1}=\frac{(a+b)z+a\varphi ^{-1}-b\varphi}{1+z-z^2}=\frac{1}{1+z-z^2}$

Entonces:

$a+b=0$

$a\varphi ^{-1}-b\varphi=1$

$\left (\begin{matrix}
1 & 1 & 0 \\
\varphi ^{-1} & -\varphi & 1 \\
\end{matrix}\right )$

$\left (\begin{matrix}
1 & 1 & 0 \\
0 & 1\times \left (-\varphi \right )-1\times \varphi ^{-1} & 1\times 1-0\times \varphi \\
\end{matrix}\right )$

$\left (\begin{matrix}
1 & 1 & 0 \\
0 & -\varphi -\varphi ^{-1} & 1 \\
\end{matrix}\right )$

$\left (\begin{matrix}
1 & 1 & 0 \\
0 & -\varphi -\left (\varphi -1\right ) & 1 \\
\end{matrix}\right )$

$\left (\begin{matrix}
1 & 1 & 0 \\
0 & -2\varphi +1 & 1 \\
\end{matrix}\right )$

$\left (\begin{matrix}
1 & 1 & 0 \\
0 & 1 & \frac{1}{-2\varphi +1} \\
\end{matrix}\right )$

$\left (\begin{matrix}
1 & 1 & 0 \\
0 & 1 & -\frac{1}{2\varphi -1} \\
\end{matrix}\right )$

$\left (\begin{matrix}
1 & 0 & 0-\left (-\frac{1}{2\varphi -1}\right ) \\
0 & 1 & -\frac{1}{2\varphi -1} \\
\end{matrix}\right )$

$\left (\begin{matrix}
1 & 0 & \frac{1}{2\varphi -1} \\
0 & 1 & -\frac{1}{2\varphi -1} \\
\end{matrix}\right )$

$\Rightarrow a=\frac{1}{2\varphi -1},~b=-\frac{1}{2\varphi -1}$
$\frac{z}{1+z-z^2}= \frac{a}{z-\varphi}+\frac{b}{z+\varphi ^{-1}}$

$\frac{Z\left \{F_n\right \}}{z}= \frac{a}{z-\varphi}+\frac{b}{z+\varphi ^{-1}}$

$\frac{Z\left \{F_n\right \}}{z}=\frac{\frac{1}{2\varphi -1}}{z-\varphi}+\frac{-\frac{1}{2\varphi -1}}{z+\varphi ^{-1}}$

$Z\left \{F_n\right \}=z\left (\frac{1}{\left (2\varphi -1\right )\left (z-\varphi\right )}-\frac{1}{\left (2\varphi -1\right )\left (z+\varphi ^{-1}\right )}\right )$

$Z\left \{F_n\right \}=\frac{1}{2\varphi -1}\left (\frac{z}{z-\varphi}-\frac{z}{z+\varphi ^{-1}}\right )$

Aplicamos la Anti-Transformada $Z^{-1}$ miembro a miembro:

$Z^{-1}\left \{Z\left \{F_n\right \}\right \}=Z^{-1}\left \{\frac{1}{2\varphi -1}\left (\frac{z}{z-\varphi}-\frac{z}{z+\varphi ^{-1}}\right )\right \}$

$F_n=\frac{1}{2\varphi -1}Z^{-1}\left (\frac{z}{z-\varphi}-\frac{z}{z+\varphi ^{-1}}\right )$

$F_n=\frac{1}{2\varphi -1}\left (Z^{-1}\left (\frac{z}{z-\varphi}\right )-Z^{-1}\left (\frac{z}{z-\left (-\varphi ^{-1}\right )}\right )\right )$

Recordamos que $Z^{-1}\left (\frac{z}{z-a}\right )=a^n$
Spoiler: mostrar
$Z\left \{a^n\right \}=\sum \limits _{k=0}^{\infty}\frac{a^k}{z^k}$

$Z\left \{a^n\right \}=\sum \limits _{k=0}^{\infty}\left (\frac{a}{z}\right )^k$

$Z\left \{a^n\right \}=\lim \limits _{n\to \infty}\frac{\left (\frac{a}{z}\right )^{n+1}-\left (\frac{a}{z}\right )^0}{\frac{a}{z}-1}$

$Z\left \{a^n\right \}=\lim \limits _{n\to \infty}\frac{\left (\frac{a}{z}\right )^{n+1}-1}{\frac{a -z}{z}}$

Si $\left |\frac{a}{z}\right |\le 1,~\left |\frac{a}{z}\right |\neq 1$

$\Rightarrow \lim \limits _{n\to \infty}\left (\frac{a}{z}\right )^n=0$

$\Rightarrow \lim \limits _{n\to \infty}\frac{\left (\frac{a}{z}\right )^{n+1}-1}{\frac{a-z}{z}}=\frac{0-1}{\frac{a-z}{z}}$

$Z\left \{a^n\right \}=\frac{-1}{\frac{a-z}{z}}$

$Z\left \{a^n\right \}=\frac{-z}{a-z}$

$Z\left \{a^n\right \}=\frac{z}{z-a}$

$Z^{-1}\left \{Z\left \{a^n\right \}\right \}=Z^{-1}\left \{\frac{z}{z-a}\right \}$

$a^n=Z^{-1}\left \{\frac{z}{z-a}\right \}$
$F_n=\frac{1}{2\varphi -1}\left (\varphi ^n-\left (-\varphi ^{-1}\right )^n\right )$

$F_n=\frac{\varphi ^n-\left (-\varphi \right )^{-n}}{2\varphi -1}$

Con esta fórmula se puede extender la definición de $F_n$:

$F:\mathbb{Z}\to \text{Im}\in \mathbb{Z}~/~F_n+F_{n+1}=F_{n+2},~F_0=0,~F_1=1$
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Fórmula de de Moivre & Binet (n-ésimo término de la sucesión de Fibonacci)

Mensaje sin leer por Gianni De Rico »

♪♫ do re mi función lineal ♪♫
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Fórmula de de Moivre & Binet (n-ésimo término de la sucesión de Fibonacci)

Mensaje sin leer por Gianni De Rico »

Ya que está en Nivel 4, dejo esta demo porque me pareció interesante
Spoiler: mostrar
Sean $F=\left (\begin{matrix}1&1\\1&0\end{matrix}\right )$ la matriz de Fibonacci, $\{f_n\}$ la sucesión de Fibonacci, y $u_n=(f_{n+1},f_n)^t$. Tenemos entonces que $u_n=F^nu_0$.
Notemos ahora que los autovalores de $F$ son $\varphi$ y $(-\varphi )^{-1}$, de donde los autovalores de $F^n$ son $\varphi ^n$ y $\left ((-\varphi )^{-1}\right )^n$. Además, $(\varphi ,1)^t$ y $\left ((-\varphi )^{-1},1\right )^t$ son autovectores de $F$ correspondientes a $\varphi$ y $(-\varphi )^{-1}$, respectivamente, de donde son autovectores de $F^n$ correspondientes a $\varphi ^n$ y $\left ((-\varphi )^{-1}\right )^n$, respectivamente. Por último, $u_0=\frac{1}{\sqrt{5}}(\varphi ,1)^t-\frac{1}{\sqrt{5}}\left ((-\varphi )^{-1},1\right )^t$.
Entonces\begin{align*}u_n & =F^nu_0 \\
& =F^n\left(\frac{1}{\sqrt{5}}(\varphi ,1)^t-\frac{1}{\sqrt{5}}\left ((-\varphi )^{-1},1\right )^t\right ) \\
& =\frac{1}{\sqrt{5}}F^n(\varphi ,1)^t-\frac{1}{\sqrt{5}}F^n\left ((-\varphi )^{-1},1\right )^t \\
& =\frac{1}{\sqrt{5}}\varphi ^n(\varphi ,1)^t-\frac{1}{\sqrt{5}}\left ((-\varphi )^{-1}\right )^n\left ((-\varphi )^{-1},1\right )^t \\
& =\left (\frac{\varphi ^{n+1}-\left ((-\varphi )^{-1}\right )^{n+1}}{\sqrt{5}},\frac{\varphi ^n-\left ((-\varphi )^{-1}\right )^n}{\sqrt{5}}\right )^t
\end{align*}pero $u_n=(f_{n+1},f_n)^t$, de donde$$f_n=\frac{\varphi ^n-(-\varphi )^{-n}}{\sqrt{5}}=\frac{1}{\sqrt{5}}\left (\left (\frac{1+\sqrt{5}}{2}\right )^n-\left (\frac{1-\sqrt{5}}{2}\right )^n\right )$$y estamos.
♪♫ do re mi función lineal ♪♫
Responder