1
$\begingroup$

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)

$\endgroup$
5
  • $\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$ Commented Jul 3, 2016 at 18:15
  • $\begingroup$ @fleablood Now I feel ridiculous for asking, but thanks a ton. $\endgroup$ Commented Jul 3, 2016 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$ Commented Jul 3, 2016 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$ Commented Jul 3, 2016 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$ Commented Jul 3, 2016 at 18:26

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.