1
$\begingroup$

So I am having trouble proving that $F(n)>2n$ for all $n>7$. for base case I took n=8, so obviously $f(8)=21> 2*8= 16$ Assuming$ f(n)>2n$
$f(n+1)>2(n+1)$
$f(n)+f(n-1)>2n+2$
$f(n)> 2n$ according to the induction hypothesis and since $n>7$ ,$f(n-1)$ should be at least $f(7)$ and therefore more than 2, however I'm not sure if this is the correct way to prove this by induction on n...

$\endgroup$
5
  • 2
    $\begingroup$ please use mathjax syntax otherwise it is tedious to read. (He was named Fibonacci anyway) ;-) $\endgroup$
    – trying
    Sep 9, 2017 at 19:36
  • 2
    $\begingroup$ The easiest way is to use a variant of the induction slightly different to the usual induction (See my answer) $\endgroup$
    – Peter
    Sep 9, 2017 at 19:43
  • 1
    $\begingroup$ When doing proofs by induction on the Fibonacci sequence it is almost always the variant that you apply the induction hypothesis to two previous cases (so that you can use the recurrence relation). For the argument to have a solid footing it is then imperative that you check two smallest indices separately, i.e. there will be two base cases. $\endgroup$ Sep 9, 2017 at 19:52
  • 2
    $\begingroup$ Your method is ok (if you already know that $F(n)\ge2$ for $n\ge7$) $\endgroup$ Sep 9, 2017 at 19:58
  • $\begingroup$ @HagenvonEitzen I know that because since we're only above n>7, we know that F(8+) will be more than 2, I'm not sure if I need to prove this somehow. $\endgroup$
    – Lola1984
    Sep 9, 2017 at 22:51

3 Answers 3

2
$\begingroup$

Assume $$f_n>2n$$ and $$f_{n+1}>2(n+1)=2n+2$$ for $n\ge 8$.Then you have

$$f_{n+2}=f_n+f_{n+1}>2n+2n+2>2n+4=2(n+2)$$

together with the start $f_8>16$ and $f_9>18$ this completes the proof

$\endgroup$
3
  • $\begingroup$ How do you know that 2n+2n+2 > 2n+4 ? I mean we get that 4n+2 >2n +4 and how do you know that? $\endgroup$
    – Lola1984
    Sep 9, 2017 at 22:50
  • $\begingroup$ @user381994 We have $2n+2n+2=2n+(2n+2)>2n+4$ for $n>1$. And the equation $4n+2>2n+4$ you mentioned is equivalent to $2n>2$ and therefore $n>1$. And $n>1$ is obvious because we assumed $n\ge 8$ $\endgroup$
    – Peter
    Sep 11, 2017 at 11:22
  • $\begingroup$ Instead of "equation" in my last comment, it should, of course be "inequality" $\endgroup$
    – Peter
    Sep 11, 2017 at 12:13
2
$\begingroup$

Another way : It is easier to prove : $$\begin{array}{l} {F_n} = \frac{{{\varphi ^n} - {\psi ^n}}}{{\varphi - \psi }} = \frac{{{\varphi ^n} - {\psi ^n}}}{{\sqrt 5 }} > \frac{{{\varphi ^n}}}{{\sqrt 5 }} = \frac{{{{(\frac{{1 + \sqrt 5 }}{2})}^n}}}{{\sqrt 5 }}\\ \varphi = \frac{{1 + \sqrt 5 }}{2} \approx 1.61803{\mkern 1mu} 39887 \cdots \end{array}$$ so prove that $$\forall n>7 :F_n>\frac{{{{(\frac{{1 + \sqrt 5 }}{2})}^n}}}{{\sqrt 5 }}>2n$$ so $$p(8) \space \frac{{{{(\frac{{1 + \sqrt 5 }}{2})}^8}}}{{\sqrt 5 }}>2\times 8 \\20.57>16 \checkmark $$ $$p(n) :\space \frac{{{{(\frac{{1 + \sqrt 5 }}{2})}^n}}}{{\sqrt 5 }}>2n\\p(n+1): \space \frac{{{{(\frac{{1 + \sqrt 5 }}{2})}^{n+1}}}}{{\sqrt 5 }}>2(n+1)$$ multiply $p(n) $ by $\frac{{1 + \sqrt 5 }}{2}$ $$\space \frac{{{{(\frac{{1 + \sqrt 5 }}{2})}^{n+1}}}}{{\sqrt 5 }}>2n(\frac{{1 + \sqrt 5 }}{2})>2n(1.5)=\underbrace{3n >2n+2}_{\forall n>7} \checkmark$$

$\endgroup$
1
$\begingroup$

Consider the following proposition (P):

For all $n\in \Bbb N$ if $F_{n+8} > 2(n+8)$ and $F_{n+7} > 2(n+7)$ then $F_{n+9} > 2(n+9)$.

Let us prove $P$ by induction: The basis is easy: For $n=1$ this becomes $F_{10} > 2(10)$ or $55> 20$.

Now assume (P) holds for all $n<k$. Then $$ F_k = F_{k-1} + F_{k-2} > 2(k+8) +2(k+7) > 4k+30 > 2k+18 = 2(k+9) $$ so (P) holds for $n=k$ as well; this establishes induction.

Thus (P) holds for all $n \in \Bbb N$, which in turns says that $\forall n\geq 9 : F_n > 2n$.

The proof of the original statement is then completed by noting that the only omitted cases is $n=8$ and $F_8 = 21 > 16$.

$\endgroup$

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.