Here, $\phi$ is the golden ratio and $f_n$ is the $n^{th}$ Fibonacci number. The formula I'm using is actually the closed form of the Lucas numbers.
Let $n = 1$. Then $f_n = 1$ and $\phi + 1 – \phi = 1$. Thus, the case holds where $n = 1$, establishing our base case.
Assume the case holds for all natural numbers less than or equal to $k$. Then $f_{n+1} = f_n + f_{n-1} = \phi^k + (1-\phi)^k + \phi^{k-1} + (1-\phi)^{k-1} = \phi^{k-1}(1 + \phi) + (1-\phi)^{k-1}(2-\phi) = \phi^{k-1}\phi^2 + (1 – \phi)^{k-1}(1-\phi)^2 = \phi^{k+1} + (1-\phi)^{k+1}$. Thus the case holds where $n = k+1$. By mathematical induction, the claim holds for all $n \in N$.
However, $f_3 =2$ and $\phi^3 + (1-\phi)^3 = 4$. Why is this?
Best Answer
Your inductive step is just a verification that $\rm\:g_n = \phi^n + (1-\phi)^n\:$ also satsifies the fibonacci recurrence $\rm\:f_{n+2} = f_{n+1}\! + f_{n}.\,$ The solutions of such linear second-order homogeneous difference equations are uniquely determined by the initial values $\rm\,f_0, f_1,\:$ as a trivial inductive proof shows. However, your "base case" only verifies that they agree for $\rm\:n = 1.\:$ But they disagree for $\rm\:n = 0\:$ since $\rm\:f_0 = 0\:$ but $\rm\:g_0 = \phi^0 + (1-\phi)^0 = 2.\:$ These initial conditions define the Lucas numbers.
So why does your proof fail? If you examine the proof of the inductive step for $\rm\:n = 1\:$ you'll note that, to deduce the truth of the identity for $\rm\:n = 2,\:$ it employs the truth at $\rm\;n = 1\:$ and $\rm\:n = 0.\:$ However, you never proved that it is true for $\rm\:n = 0;\:$ in fact, as we saw, it is not: $\rm\:f_0\ne g_0.$