Prove that the Fibonacci recursion diverges

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

$f(1)=f(2)=1. f(n)=f(n-1)+f(n-2)$

The sum of two positive numbers is always positive so $\forall n, f(n)>0$.

Since $f(n)-f(n-1)=f(n-2)>0$, then $f(n)$ is increasing. A stronger statement can be made.

$f(n)=2f(n-2)+f(n-3)\implies f(n)>2f(n-2)\implies f(n+2)>2f(n)\implies f(n+2)>2f(n)>4f(n-2)$

$f(n+2k)>4^kf(n-2)\implies f(3+2k)>4^k$

$4^k$ diverges, so f diverges roughly as a geometric sequence.

$f(N)>2^{(N-3)}$

For any $M>0$ pick integer $n>N=\ln{M}/\ln{2}+3$. Then $f(n)>M$. By definition then, $f(n)$ diverges.