# Fibonacci Numbers $ F_i = \begin{cases} 0 & i = 0, \\ 1 & i = 1, \\ F_{i-1} + F_{i-2} & i \ge 2 \end{cases} $ With [[golden-ratio]] defined as $\phi$, and its conjugate $\hat\phi$. $ F_i = \frac{\phi^i - {\hat\phi}^i}{\sqrt5} $ Since $\left|\hat\phi\right| < 1$, we also have $ F_i = \left\lfloor\frac{\phi^i}{\sqrt5} + \frac12\right\rfloor $ ## Solution - Utilize [[generating-function]]. - Map each term to polynomial, i.e. define a sequence $\sum_i F_ix^i$. - Rewrite the recurrence relation, and solve for the $x$. - Plug $x$ back in to derive $F_i$.