# Prove $a_n=1+\frac{a_{n-1}}{1+a_{n-1}}$ increasing

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!

• Hem, by proving that $a_n>a_{n-1}$maybe ? – Yves Daoust Jun 6 '14 at 17:30
• I know but how? – 52145208 Jun 6 '14 at 17:32
• @boywholived Yes, it's convergent in a few terms. I computed it in R and see the result. – 52145208 Jun 6 '14 at 17:35
• @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}$. – jdoicj Jun 6 '14 at 17:40
• If you want to downvote a legitimate and mathematically correct answer, then I don't have to provide it. – heropup Jun 6 '14 at 17:56

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.500000 1.600000 1.615385 1.617647 1.617978 1.618026 1.618033 1.618034
 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034
 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034
 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034
 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034
 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034
 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): 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}$.

• I think I understand it, thanks! – 52145208 Jun 7 '14 at 5:42

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.

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

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}

• But it's based on you know $\frac{\sqrt5 +1}{2}$? – 52145208 Jun 6 '14 at 18:09
• 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. – punctured dusk Jun 6 '14 at 19:09
• @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. – Leucippus Jun 6 '14 at 19:51
• I think he does not quite familiar with Fibonacci, which means he needs a simple way to do it. Anyway, this method is good! – zhaoyin.usm Jun 7 '14 at 5:35