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