3
$\begingroup$

There is a homework question in Calculus-1 course:

Calculate the limit of $\{a_n\}$: $$a_1=1,\ a_n=1+\frac{a_{n-1}}{1+a_{n-1}}$$

I think the key points are bounded and increasing, and I have proved that $$a_n\in(1, 2)$$

If I knew it's increasing then $$a=1+\frac{a}{1+a}\Rightarrow\lim a_n=\frac{\sqrt5+1}{2}$$

My question is How to Prove it's increasing?

I tried it in two ways: $$a_{n+1}-a_n=1+\frac{a_n}{1+a_n}-a_n=\frac{-a^2_n+a_n+1}{1+a_n}$$ But how to prove that $-a^2_n+a_n+1>0$?

Another way is $$\frac{a_{n+1}}{a_n}=\frac{1}{a_n}+\frac{1}{1+a_n}=\frac{1+2a_n}{a_n+a^2_n}$$ But how to prove that $1+2a_n>a_n+a^2_n$?

This is not a proof question which means $\frac{\sqrt5+1}{2}$ is not a known result.

Thank you!

$\endgroup$
6
  • $\begingroup$ Hem, by proving that $a_n>a_{n-1}$maybe ? $\endgroup$
    – user65203
    Jun 6 '14 at 17:30
  • $\begingroup$ I know but how? $\endgroup$
    – zhaoyin
    Jun 6 '14 at 17:32
  • $\begingroup$ @boywholived Yes, it's convergent in a few terms. I computed it in R and see the result. $\endgroup$
    – zhaoyin
    Jun 6 '14 at 17:35
  • $\begingroup$ @52145208. I'm sorry, I missed the point that $a_1=1$(in my previous comment). One way to prove your statement is to assume that $a_n<\frac{\sqrt{5}+1}{2}$, and then prove that $a_{n+1}<\frac{\sqrt{5}+1}{2}$ and that $a_{n+1}>a_{n}$. $\endgroup$
    – hrkrshnn
    Jun 6 '14 at 17:40
  • $\begingroup$ If you want to downvote a legitimate and mathematically correct answer, then I don't have to provide it. $\endgroup$
    – heropup
    Jun 6 '14 at 17:56
4
$\begingroup$

First, we prove that $a_n$ is bounded above. Obviously, $a_n = 1+ \frac{a_{n-1}}{a_{n-1}+1} < 2$.

To prove that the sequence is increasing, we can just use induction. The base cases are trivial so suppose the claim holds for all naturals $ \le k$. Then $a_{k+1}-a_k = \frac{a_k}{1+a_k} - \frac{a_{k-1}}{1+a_{k-1}} = \frac{a_k(1+a_{k-1})-a_{k-1}(1+a_k)}{(1+a_k)(1+a_{k-1})}$.

The numerator is $a_k-a_{k-1}$ which by the inductive hypothesis is $> 0$ so we are done.

$\endgroup$
3
  • $\begingroup$ I don't think inductive proof can be used here. $\endgroup$
    – zhaoyin
    Jun 6 '14 at 17:39
  • $\begingroup$ I think you can prove it directly, e.g. making difference. $\endgroup$ Jun 6 '14 at 17:48
  • $\begingroup$ @52145208, what do you mean an inductive proof can't be used here? Sandeep provides one! $\endgroup$ Jun 6 '14 at 19:08
2
$\begingroup$

I think you can follow this way to prove it:

Firstly, showing it's bounded. You can list the first several terms of this sequence, I used R to do it:

a <- 1
b <- NULL
for (i in 1:50){
  b[i] <- 1 + a / (1 + a)
  a <- b[i]
}
b
[1] 1.500000 1.600000 1.615385 1.617647 1.617978 1.618026 1.618033 1.618034
[9] 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034
[17] 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034
[25] 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034
[33] 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034
[41] 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034
[49] 1.618034 1.618034

This shows that there Should be a limit of this sequence, say $a$. Then we compute it using the method you mentioned in your post: $$a=1+\frac{a}{1+a}\Rightarrow a=\frac{1+\sqrt5}{2}$$ Note that this is not a Proof but only a guess (i.e. we want to know the boundary). Now let's prove the sequence is bounded by $\frac{1+\sqrt5}{2}$, here is an inductive way: $$x_1=1<\frac{1+\sqrt5}{2},\ \text{Assuming that}\ x_n<\frac{1+\sqrt5}{2}$$ $$\Rightarrow x_{n+1}=1+\frac{x_n}{1+x_n}<1+\frac{\frac{1+\sqrt5}{2}}{1+\frac{1+\sqrt5}{2}}=\frac{1+\sqrt5}{2}$$ Note that $\frac{x}{1+x}$is increasing when $x\ge1$ (or you can use simply derivative way to prove it):

enter image description here

We have proved $x_n$ is bounded by $\frac{1+\sqrt5}{2}$ till now.

Next, we prove it's increasing. According to it's bounded by $\frac{1+\sqrt5}{2}$ (i.e. $x_n<\frac{1+\sqrt5}{2}$), we have $$\frac{x_{n+1}}{x_n}=\frac{1}{x_n}+\frac{1}{1+x_n}>\frac{1}{\frac{1+\sqrt5}{2}}+\frac{1}{1+\frac{1+\sqrt5}{2}}=1$$ $$\Rightarrow x_{n+1}>x_n$$

Based on the above, we can conclude that it's increasing and bounded and thus its limit is $\frac{1+\sqrt5}{2}$.

$\endgroup$
1
  • $\begingroup$ I think I understand it, thanks! $\endgroup$
    – zhaoyin
    Jun 7 '14 at 5:42
2
$\begingroup$

Consider the sequence \begin{align} a_{n} = 1 + \frac{a_{n-1}}{1+a_{n-1}} \end{align} where $a_{1} = 1$.

Let $2 \alpha = 1 + \sqrt{5}$ and $2 \beta = 1-\sqrt{5}$. It is seen that $\alpha > \beta$ and $\beta^{n} \rightarrow 0$ as $n \rightarrow \infty$. Now, the terms of $a_{n}$ are $a_{n} \in \{ 1, 3/2, 8/5, \cdots \}$ which are seen to be the Fibonacci numbers, and in general \begin{align} a_{n} = \frac{F_{2n}}{F_{2n-1}}. \end{align} Since $\sqrt{5} F_{n} = \alpha^{n} - \beta^{n}$ then \begin{align} a_{n} = \frac{\alpha^{2n} - \beta^{2n}}{\alpha^{2n-1} - \beta^{2n-1}} = \alpha \ \frac{1 - \left(\frac{\beta}{\alpha} \right)^{2n}}{1 - \left(\frac{\beta}{\alpha} \right)^{2n-1}} . \end{align} Taking the limit as $n \rightarrow \infty$ leads to \begin{align} \lim_{n \rightarrow \infty} a_{n} = \alpha = \frac{1+\sqrt{5}}{2}. \end{align}

$\endgroup$
4
  • $\begingroup$ But it's based on you know $\frac{\sqrt5 +1}{2}$? $\endgroup$
    – zhaoyin
    Jun 6 '14 at 18:09
  • $\begingroup$ No, in fact he proves (or skips the proof because it isn't too difficult with induction) a closed form for $a_n$, namely $a_n=\frac{F_{2n}}{F_{2n+1}}$. Then we can use Binet's formula (in which $\frac{1+\sqrt5}2$ appears, but you can think of it as being coincidence (which it is not)) to evaluate the limit. $\endgroup$ Jun 6 '14 at 19:09
  • $\begingroup$ @52145208 "Barto" is correct. What I skipped is how the Fibonacci form actually is. I skipped it by mentioning Fibonacci numbers. In the section "Relation to the Golden Ratio" of en.wikipedia.org/wiki/Fibonacci_number The Binet formula, of which I used, can be found. $\endgroup$
    – Leucippus
    Jun 6 '14 at 19:51
  • 1
    $\begingroup$ I think he does not quite familiar with Fibonacci, which means he needs a simple way to do it. Anyway, this method is good! $\endgroup$ Jun 7 '14 at 5:35

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.