Prove by induction that the $i$th Fibonacci number satisfies the equality

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

where $\phi$ is the golden ratio and $\hat{\phi}$ is its conjugate.

For our base case, we need two values of $F$:

$$F_0 = \frac{\phi^0 - \hat{\phi^0}}{\sqrt{5}} = \frac{1 - 1}{\sqrt{5}} = 0$$ $$F_1 = \frac{\phi^1 - \hat{\phi^1}}{\sqrt{5}} = \frac{\frac{1 + \sqrt{5}}{2} - \frac{1 - \sqrt{5}}{2}}{\sqrt{5}} = \frac{1 + \sqrt{5} - 1 + \sqrt{5}}{2\sqrt{5}} = \frac{2\sqrt{5}}{2\sqrt{5}} = 1$$

For the inductive step, recall that $F_i = F_{i-1} + F_{i-2}$ for $i \geq 2$:

$$\begin{equation} \begin{split} F_i & = \frac{\phi^{i-1} - \hat{\phi}{}^{i-1}}{\sqrt{5}} + \frac{\phi^{i-2} - \hat{\phi}{}^{i-2}}{\sqrt{5}} \\ & = \frac{\phi^{i-1} + \phi^{i-2} - \hat{\phi}{}^{i-1} - \hat{\phi}{}^{i-2}}{\sqrt{5}} \\ & = \frac{\phi^{i-2}(\phi + 1) - \hat{\phi}{}^{i-2}(\hat{\phi} + 1)}{\sqrt{5}} \\ & = \frac{\phi^{i-2}\phi^2 - \hat{\phi}{}^{i-2}\hat{\phi}{}^{2}}{\sqrt{5}} \\ & = \frac{\phi^i - \hat{\phi}{}^i}{\sqrt{5}} \\ \end{split} \end{equation}$$