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.