1

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...

Lola1984
  • 313
  • 2
    please use mathjax syntax otherwise it is tedious to read. (He was named Fibonacci anyway) ;-) – trying Sep 09 '17 at 19:36
  • 2
    The easiest way is to use a variant of the induction slightly different to the usual induction (See my answer) – Peter Sep 09 '17 at 19:43
  • 1
    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. – Jyrki Lahtonen Sep 09 '17 at 19:52
  • 2
    Your method is ok (if you already know that $F(n)\ge2$ for $n\ge7$) – Hagen von Eitzen Sep 09 '17 at 19:58
  • @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. – Lola1984 Sep 09 '17 at 22:51

3 Answers3

2

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

Peter
  • 84,454
  • 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? – Lola1984 Sep 09 '17 at 22:50
  • @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$ – Peter Sep 11 '17 at 11:22
  • Instead of "equation" in my last comment, it should, of course be "inequality" – Peter Sep 11 '17 at 12:13
2

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$$

Khosrotash
  • 24,922
1

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$.

Mark Fischler
  • 41,743