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}\]