fibonacci

Fibonacci Numbers

$$F_i=\{\begin{array}{ll}0& i=0,\\ 1& i=1,\\ F_{i-1}+F_{i-2}& i\ge 2\end{array}$$

With golden-ratio defined as $\varphi$, and its conjugate $\hat{\varphi }$.

$$F_i=\frac{{\varphi }^i-{\hat{\varphi }}^i}{\sqrt{5}}$$

Since $\left|\hat{\varphi }\right|<1$, we also have

$$F_i=\lfloor \frac{{\varphi }^i}{\sqrt{5}}+\frac{1}{2}\rfloor$$

Solution

• Utilize generating-function.
• Map each term to polynomial, i.e. define a sequence ${\sum }_i{F}_i{x}^i$.
• Rewrite the recurrence relation, and solve for the $x$.
• Plug $x$ back in to derive $F_i$.