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.

From chapter text, the values of \(\phi\) and \(\hat\phi\) are as follows:

\[\phi = \frac {1 + \sqrt 5} 2 \qquad \hat\phi = \frac {1 - \sqrt 5} 2\]

And, Fibonacci series is defined by:

\[\begin {aligned} F_i = \begin {cases} 0 & \text { for } i = 0 \\ 1 & \text { for } i = 1 \\ F_{i-1} + F_{i-2} & \text { for } i \ge 2 \end {cases} \end {aligned}\]

Base Case

We need to show the equality holds for both \(i = 0\) and \(i = 1\).

\[\begin {aligned} F_0 & = \frac {\phi^0 - \hat\phi^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0 \\[2ex] F_1 & = \frac {\phi^1 - \hat\phi^1} {\sqrt 5} = \frac {\sqrt 5} {\sqrt 5} = 1 \end {aligned}\]

Inductive Step

Let us assume that the equality holds for \(i = k\) and \(i = k - 1\) such that \(k \ge 2\). We have to show that it holds for \(i = k + 1\) too.

\[\begin {aligned} F_{k + 1} & = F_k + F_{k - 1} \\ & = \frac {\phi^k - \hat\phi^k} {\sqrt 5} + \frac {\phi^{k - 1} - \hat\phi^{k - 1}} {\sqrt 5} \\ & = \frac {(\phi^k - \hat\phi^k) + (\phi^{k - 1} - \hat\phi^{k - 1})} {\sqrt 5} \\ & = \frac {(\phi^k + \phi^{k - 1}) - (\hat\phi^k + \hat\phi^{k - 1})} {\sqrt 5} \\ & = \frac {\phi^{k - 1}(\phi + 1) - \hat\phi^{k - 1}(\hat\phi + 1)} {\sqrt 5}\\ & = \frac {\phi^{k - 1}\cdot\phi^2 - \hat\phi^{k - 1}\cdot\hat\phi^2} {\sqrt 5}\\ & = \frac {\phi^{k + 1} - \hat\phi^{k + 1}} {\sqrt 5} \end {aligned}\]

So, the inequality holds for \(k + 1\) also. Hence, the proof is complete.