# Prove that the Fibonacci recursion diverges

I have this sequence with $n \in \mathbb{N}$

$f(1) = f(2) = 1$ and $f(n) = f(n-1) + f(n-2)$ for $n \ge 3$

I think this sequence is bounded below and unbounded above. So it's clear that this recursive sequence diverges.

Questions:

• Is this correct?
• How can I write my reflections down in a formally correct way?
• It should be possible to show the sequence is larger than or equal to $n-1$ using induction. – peterwhy Dec 3 '14 at 15:00
• $f(n) \geq 2f(n-2)$. – Antonio Vargas Dec 3 '14 at 15:32

If $f(1), f(2) \ge 0$ and the right hand side adds the preceding two terms (always adding previous two positives). Then isnt it obvious that $f(n+1)\gt f(n)$ for all $n\ge 2$ and that $f(n+1) - f(n) \ge f(1)$.

• $f(n+1)>f(n)$ means that $f$ is strictly increasing, which shows that it is bounded below, but it doesn't necessarily mean that $f$ is unbounded above. – KSmarts Dec 3 '14 at 15:07
• Yes, but it is growing for each $n$ by no less than $f(1)$. – CogitoErgoCogitoSum Dec 3 '14 at 15:12
• yes, good catch. up thumb. It holds for $n>2$. My mistake. – CogitoErgoCogitoSum Dec 3 '14 at 15:15
• @KSmarts Notice $f(n)$ is an integer for all $n$. So if $f(n+1)>f(n)$, then $f$ is certainly unbounded above. – Stop hurting Monica Dec 3 '14 at 15:30
• Jean-Claude. Insightful answer. Up thumb. I wish I had thought of that. – CogitoErgoCogitoSum Dec 3 '14 at 17:04

Hint

Show by induction that $f(n)$ is increasing. Thus, $f(n)\ge f(1)$ which shows that it is bounded from below.

Show by induction that $f(n)\ge n-1.$ Thus, $f(n)$ is not bounded from above. (This also shows that $f(n)$ is bounded from below, since $f(n)\ge n-1\ge 0.$)

Proof by induction for lower bound:

• Assume, that $f(k)>0$ for $k\leq n$
• $f(1)>0$ and $f(2)>0$
• Then $f(n+1)=f(n)+f(n-1)>0$.

Proof for divergence by induction:

• Assume, that $f(k)\geq k$ for $5\leq k\leq n$
• $f(5)\geq 5$ and $f(6)\geq 6$.
• $f(n+1)=f(n)+f(n-1)\geq n+(n-1)=2n-1\rightarrow \infty$ for $n\rightarrow \infty$.

Of course, you would need to write down the steps in a more formal way.

• I'm sorry, you're correct. This only holds true for $n>4$. – k1next Dec 3 '14 at 16:16

Obviously $f(n)\geq 1$. Assume to the contrary that it converges to some $l$. By that trivial observation $l\geq 1.$ Then $\lim_{n\to\infty}f(n) = \lim_{n\to\infty}f(n-1) +\lim_{n\to\infty} f(n-2)\Rightarrow2l=l\Rightarrow l=0$ Contradiction!!