# 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 ?
– user65203
Jun 6 '14 at 17:30
• I know but how? Jun 6 '14 at 17:32
• @boywholived Yes, it's convergent in a few terms. I computed it in R and see the result. 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}$. 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. Jun 6 '14 at 17:56

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. Jun 6 '14 at 17:39
• I think you can prove it directly, e.g. making difference. Jun 6 '14 at 17:48
• @52145208, what do you mean an inductive proof can't be used here? Sandeep provides one! Jun 6 '14 at 19:08

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):

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! Jun 7 '14 at 5:42

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}$? 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. 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. 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! Jun 7 '14 at 5:35