Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Problem

I need to determine for what natural numbers is $2n < F_n$, where $F_n$ is the $n^{th}$ Fibonacci number determined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1}+F_{n-2}$. I then need to prove my findings through strong induction.

What I found

I found that the inequality is true for all $n >= 8$.

My attempt at proving by induction

Basis: $2(8) < F_8$ = TRUE

Assume: $2(k) < F_k$

Show: $2(k) < F_k$ implies $2(k+1) < F_{k+1}$

$2(k+1) = 2k + 2 < F_k + F_{k-1} = F_{k+1}$

Thus

$2(k+1) < F_{k+1}$

Logic:

$2k < F_k$ by induction hypothesis

$2 < F_{k-1}$ because $F_{k-1}$ is at least $13$ when $k>=8$

$F_{k+1}$ is $F_k + F_{k-1}$.

Is my proof correct? Is this considered strong induction?

share|improve this question
1  
You should have $F_k + F_{k - 1} = F_{k + 1}$, not $<$ right below your "Show" line. Otherwise, this looks correct. –  T. Bongers Jul 25 '13 at 3:15
    
Thanks. But is this considered strong induction? –  user87509 Jul 25 '13 at 3:16
    
@Adriano How would I prove this with strong induction? Will you leave an answer with example? –  user87509 Jul 25 '13 at 3:35
add comment

3 Answers

up vote 1 down vote accepted

IIRC, strong induction is when the induction depends on more than just the preceding value. In this case, you use the hypothesis for $k$ but not for any earlier values. Instead, you use a much weaker result ($F_{k-1} > 2$) for the earlier value.

So, I would not call this strong induction.

If you use the hypothesis ($F_n > 2n$) for $both$ $k$ and $k-1$, the induction works because $F_k > 2k$ and $F_{k-1} > 2(k-1)$ together imply $F_{k+1} = F_k+F_{k-1} > 2k + 2(k-1) = 4k-2 > 2(k+1) $ when $k \ge 3$.

Note that the induction step works when $k \ge 3$ but the induction hypothesis is true only when $k \ge 8$. So the first case where you can do the induction is $k = 9$, because you use the truth for $k=8$ and $k=9$ to prove it for $k=10$.

I would call this moderate induction, since it depends on the previous two cases being true.

share|improve this answer
    
Wouldn't the induction step also work when $k=2$ (even though the induction hypothesis doesn't work for $k<8$)? –  Adriano Jul 25 '13 at 4:02
    
Thank you very much! I feel like I am learning this! –  user87509 Jul 25 '13 at 7:51
    
What is needed is $4k-2>2(k+1)$ and this not true for $k=2$. –  marty cohen Jul 25 '13 at 13:36
add comment

Your proof is great. Here's how you would explicitly use strong induction. Note that you have already proved the base case for when $n=8$.

Induction Hypothesis: Assume that $F_n>2n$ holds true for all $n\in\{8,...,k\}$, where $k\ge8$.

It remains to prove the inequality true for $n=k+1$. Observe that: $$ \begin{align*} F_{k+1} &= F_k + F_{k-1} \\ &> 2k + 2(k-1) & \text{by the induction hypothesis} \\ &\ge 2k + 2(8-1) & \text{since } k \ge8 \\ &= 2k+14 \\ &> 2k+2 \\ &= 2(k+1) \\ \end{align*} $$ as desired. This completes the induction.

share|improve this answer
    
Thank you for posting this. –  user87509 Jul 25 '13 at 6:56
    
@positiveimpact No problem. =] –  Adriano Jul 25 '13 at 7:08
add comment

We will change the indexing slightly to make it look like archetypal strong induction.

We show that if the result holds for all $i$ such that $8\le i \lt k$ then it holds at $k$.

Because it holds at for all such $i$, it holds in particular at $k-1$. Now argue as you did (with minor index shift) that since $F_{k-1} \gt 2(k-1)$ and $2\lt F_{k-2}$, we have $2k=2(k-1)+2\lt F_{k-1}+F_{k-2}=F_k$.

Of course we have not used the full strength of the induction hypothesis, but we have written out things in strong induction style.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.