A famous [[Recurrence Relation]] / [[Sequence]] where $F_n$ is the sum of the previous two elements.
$ \huge
F_{n} = F_{n-1} + F_{n-2}
$
Where $F_0=0$ and $F_{1}=1$.
$ \huge
F_{n} = \frac{1}{\sqrt{ 5 }}\pa{ \phi^n - \pa{\frac{-1}{\phi}}^n }
$
Where $\phi$ is the [[Golden Ratio]].
### Properties
The limit of the ratio $\frac{F_{n+1}}{F_{n}}$ is the [[Golden Ratio]] $\phi$.
$\huge \lim_{ n \to \infty } \frac{F_{n+1}}{F_{n}} = \phi $
>[!tldr]- Proof
>$\small \begin{align}
>
>\lim_{ n \to \infty } \frac{F_{n+1}}{F_{n}} &=
>\lim_{ n \to \infty }
> \frac{{\frac{1}{\sqrt{ 5 }}\pa{ \phi^{n+1} - \pa{\frac{-1}{\phi}}^{n+1} }}}{{\frac{1}{\sqrt{ 5 }}\pa{ \phi^{n} - \pa{\frac{-1}{\phi}}^{n} }}} \\
>
>&= \lim_{ n \to \infty } \frac{\phi^{n+1} - \pa{\frac{-1}{\phi}}^{n+1}}{\phi^{n} - \pa{\frac{-1}{\phi}}^{n}} \\
>
>&= \lim_{ n \to \infty } \frac{
>
>\phi^{n+1} - \phi\pa{-\frac{1}{\phi}}^n +
>
>\phi\pa{-\frac{1}{\phi}}^n -\pa{-\frac{1}{\phi}}^{n+1}
>}{
>\phi^{n} - \pa{\frac{-1}{\phi}}^{n}
>} \\
>
>&= \lim_{ n \to \infty }
>
>\frac{
>
>\phi\pa{\phi^n - \pa{-\frac{1}{\phi}}^n} + \left( -\frac{1}{\phi} \right)^n\pa{ \phi-\pa{-\frac{1}{\phi}} }
>
>}{ \phi^{n} - \pa{\frac{-1}{\phi}}^{n} } \\
>&=\lim_{ n \to \infty }
>
>\frac{
>\phi\left( \phi^n - \pa{-\frac{1}{\phi}}^n \right)
>}{
>\phi^n - \pa{{-\frac{1}{\phi}}}^n
>
>}
>+
>\frac{
>\left( -\frac{1}{\phi} \right)^n\pa{ \phi+{\frac{1}{\phi}} }
>}{
>\phi^n - \pa{{-\frac{1}{\phi}}}^n
>} \\
>&= \lim_{ n \to \infty }
>\phi
>+
>\frac{
>\left( -\frac{1}{\phi} \right)^n\pa{ \phi+{\frac{1}{\phi}} }
>}{
>\phi^n - \pa{{-\frac{1}{\phi}}}^n
>} \\
>
>&= \lim_{ n \to \infty }
>\phi+
>
>\frac{
>\left( -\frac{1}{\phi} \right)^n\pa{ \phi+{\frac{1}{\phi}} }
>}{
>\phi^n - \pa{{-\frac{1}{\phi}}}^n
>}
>
>\cdot \frac{
>\frac{1}{\pa{-\frac{1}{\phi}}^n}
>}{
>\frac{1}{\pa{-\frac{1}{\phi}}^n}
>} \\
>&= \lim_{ n \to \infty }
>
>\phi + \frac{\phi+\frac{1}{\phi}}{
>
>\frac{\phi^n}{\pa{-\frac{1}{\phi}}^n}
>-1
>
>}\\
>
>&= \lim_{ n \to \infty }
>
>\phi + \frac{\phi+\frac{1}{\phi}}{
>
>\pa{\frac{\phi}{{-\frac{1}{\phi}}}}^n
>-1
>
>}\\
>
>&= \lim_{ n \to \infty }
>\phi +
>\frac{\sqrt{ 5 }}{
>\pa{- \frac{3+\sqrt{ 5 }}{2} }^n - 1
>}\\
>&= \lim_{ n \to \infty }
>\phi +
>
>\lim_{ n \to \infty }
>\frac{\sqrt{ 5 }}{
>\pa{- \frac{3+\sqrt{ 5 }}{2} }^n - 1
>} \\
>&= \phi + 0 \\
>&= \phi
>
>
>\end{align}
>$
All consecutive [[Fibonacci Sequence|Fibonacci Numbers]] are [[Relatively Prime]].
$ \huge \gcd(F_{n},F_{n+1})=1 $