1
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ It should be possible to show the sequence is larger than or equal to $n-1$ using induction. $\endgroup$ – peterwhy Dec 3 '14 at 15:00
  • $\begingroup$ $f(n) \geq 2f(n-2)$. $\endgroup$ – Antonio Vargas Dec 3 '14 at 15:32
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $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. $\endgroup$ – KSmarts Dec 3 '14 at 15:07
  • $\begingroup$ Yes, but it is growing for each $n$ by no less than $f(1)$. $\endgroup$ – CogitoErgoCogitoSum Dec 3 '14 at 15:12
  • $\begingroup$ yes, good catch. up thumb. It holds for $n>2$. My mistake. $\endgroup$ – CogitoErgoCogitoSum Dec 3 '14 at 15:15
  • 1
    $\begingroup$ @KSmarts Notice $f(n)$ is an integer for all $n$. So if $f(n+1)>f(n)$, then $f$ is certainly unbounded above. $\endgroup$ – Stop hurting Monica Dec 3 '14 at 15:30
  • $\begingroup$ Jean-Claude. Insightful answer. Up thumb. I wish I had thought of that. $\endgroup$ – CogitoErgoCogitoSum Dec 3 '14 at 17:04
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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

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

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