Para discutir problemas de competencias para graduados de secundaria (Número de Oro, CIMA/Paenza, etcétera) y problemas que requieran conocimientos avanzados.
Yanes
Mensajes: 27 Registrado: Lun 05 Nov, 2018 8:59 pm
Medallas: 2
Nivel: Exolímpico
Mensaje sin leer
por Yanes » Mié 11 Dic, 2019 4:28 am
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$
Gianni De Rico
Mensajes: 2212 Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:
Mensaje sin leer
por Gianni De Rico » Sab 22 Ago, 2020 10:47 pm
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 ♪♫