# Proving i-th Fibonacci number by induction, can an inductive step be used for two sequential values?

I am working through the beginning of Introduction to Algorithms, and came across the problem

Prove by induction that the $i$-th Fibonacci number satisfies the equality $$F_{i} = \frac{\phi^{i} - \hat{\phi^{i}}}{\sqrt{5}}$$ where $\phi$ and $\hat{\phi}$ are the golden ratio and it's conjugate, respectively.

Now I know there are plenty of answers online regarding this proof, and I have already come to understand a few ways to approach it, but I am simply curious about the approach I originally took to solving the problem and whether it is valid or not.

I am fairly convinced it is invalid, but I want to double check and wonder if there is some mechanism in the proof I can change to validate it.

### My approach:

First, I proved (trivially) that both $\phi$ and $\hat{\phi}$ satisfy the equation \begin{equation} x^{2} = x+1 \tag{1} \end{equation}

Then after trivially proving the base cases for the inductive proof, for the inductive step we assume $$F_{k} = \frac{\phi^{k} - \hat{\phi^{k}}}{\sqrt{5}}$$ for some $k \in \mathbb{Z}^{+}$.

Then for $k+1$, we have \begin{align} \frac{\phi^{k+1} - \hat{\phi^{k+1}}}{\sqrt{5}} &= \frac{\phi^{k-1}\phi^{2} - \hat{\phi}^{k-1}\hat{\phi^{2}}}{\sqrt{5} } \\ &= \frac{\phi^{k-1}(\phi + 1) - \hat{\phi}^{k-1}(\hat{\phi} + 1)}{\sqrt{5}} && \text{by (1)} \\ &= \frac{\phi^{k} - \hat{\phi}^{k}}{\sqrt{5}} + \frac{\phi^{k-1} - \hat{\phi}^{k-1}}{\sqrt{5}} \\ &= F_{k} + F_{k-1} \\ &= F_{k+1} && \text{by definition} \end{align}

This looks downright incorrect to me because it implies that the inductive step holds for $k-1$, which is not permitted in inductive proofs, correct? If so, are there any measures I can take to validate this proof? I've already worked out a solution going the other way with the recurrence relation, I'm just curious how close this might be (I haven't touched inductive proofs in a while)

• Induction is a matter of assuming something is true for k. what is true for k can be anything you want. Weak induction is where you assume "prop is true for n = k". Strong induction is where you assume "prop is true for $n \le k$" Either assumption is perfectly valid if you can show that your assumption implies "prop is true for n = k + 1". So yes that is utterly acceptable. – fleablood Jul 3 '16 at 18:15
• @fleablood Now I feel ridiculous for asking, but thanks a ton. – Eric Hansen Jul 3 '16 at 18:17
• one thing you have to watch out for with strong induction is that as your only base case was $n = 1$ you can not assume if true for $n \le k$ you may NOT assume $k > 1$. If you refer to a k -1 case you must show a two base cases. Either n = 0 and n = 1 or n =1 and n = 2. – fleablood Jul 3 '16 at 18:17
• So you do have a small problem. For $k = 1$ you haven't shown that that F_0 is defined. So you must do a base base case of F_0 = 0 and property holds. Which can be a definition – fleablood Jul 3 '16 at 18:22
• @fleablood Yes yes my apologies, I should have been more clear in that respect, I proved the base cases for $F_{0}$ and $F_{1}$, showing their definition. Thanks again! – Eric Hansen Jul 3 '16 at 18:26

For $k\ge 1$, let $A_k$ be the assertion that $F_k$ and $F_{k-1}$ both satisfy the condition.
You have shown that if $A_k$ holds, then the condition is satisfied at $k+1$, and therefore that $A_{k+1}$ holds. So you have proved that $A_n$ holds for all $n$, and therefore that $F_n$ satisfies the condition for all $n$.