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)

  • $\begingroup$ 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. $\endgroup$ – fleablood Jul 3 '16 at 18:15
  • $\begingroup$ @fleablood Now I feel ridiculous for asking, but thanks a ton. $\endgroup$ – Eric Hansen Jul 3 '16 at 18:17
  • 1
    $\begingroup$ 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. $\endgroup$ – fleablood Jul 3 '16 at 18:17
  • $\begingroup$ 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 $\endgroup$ – fleablood Jul 3 '16 at 18:22
  • $\begingroup$ @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! $\endgroup$ – 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$.

For another approach that is more generally useful, please see strong induction aka complete induction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.