How to prove this recursive convergence by induction I am having difficulties in proving that the following recursive sequence converges: 
$$a_{n+1}=\frac{2a_{n}+1}{a_{n}+2} :a_{1}=0$$
I have tried proving this by mathematical induction by first proving it is increasing and secondly that it has an upper bound.
Proving it is increasing: Since $a_{2}\geq a_{1}$ then we assume that $a_{k+1}\geq a_{k}$ and try to show that it implies $a_{k+2}\geq a_{k+1}$. I try to show this below and get stuck quite quickly: 
$$a_{k+1}\geq a_{k} \Leftrightarrow 2a_{k+1}+1 \geq 2a_{k}+1$$
As you can see I cannot divide by $a_{n}+2$ to show that $a_{k+1}\geq a_{k} \implies a_{k+2}\geq a_{k+1}$. My question is therefore if I am doing something worng or if this cannot be proven by induction, and if not, which other methods exist to prove this.
 A: Sometimes the trick of these kind of recurrences is to write them in a more clarifying way. Notice that this particular case can be written as
$$\frac{a_{n}-1}{a_{n}+1}=\frac{1}{3}\bigg(\frac{a_{n-1}-1}{a_{n-1} + 1}\bigg)$$
which clearly implies that, as we iterate:
$$\frac{a_{n}-1}{a_{n}+1}=\frac{1}{3}\bigg(\frac{a_{n-1}-1}{a_{n-1} + 1}\bigg)=\dots=\frac{1}{3^{n}}\bigg(\frac{a_{0}-1}{a_0 + 1}\bigg)$$
This can be inverted to give
$$a_{n}=\frac{3^n + \frac{a_0 -1}{a_0 +1}}{3^n - \frac{a_0 -1}{a_0 +1}}$$
Which for $a_0 = 0$ clearly converges to $a_{\infty} = 1$.
A: Induction works. The plan of proof goes as follows, using induction in each step:


*

*Prove $a_n\ge 0$ for all $n$. This one is clear, given the base case $a_1\ge0$.

*Prove $a_n\le 1$ for all $n$. You can show this by noting that
$$\frac{2a_n+1}{a_n+2}\le 1$$
can be rearranged into
$$a_n\le 1$$

*Now prove that $a_n$ is increasing, using
$$
a_{n+1} - a_n = \frac{2a_n+1}{a_n+2} - \frac{a_n^2+2a_n}{a_n+2}
=\frac{1 - a_n^2}{a_n+2}$$
and the results (1) and (2) that you just proved.
A: An alternative method for this class of recurrences is to look at the function $a_{n+1}=f(a_n)$. In this case 
$$f(x)=\frac{2x+1}{x+2}$$
where
$$f'(x)=\frac{3}{(x+2)^2}$$
From this we see 2 properties


*

*$f(x)$ is ascending for $x\geq 0$

*$f(x)>0$ for $x\geq0$


Also, since $a_2=f(a_1)=\frac{1}{2}>0=a_1$, using the fact that $f(x)$ is ascending, we have $f(a_2)\geq f(a_1)$ which is equivalent to $a_3 \geq a_2$. Inductively, this leads to $a_{n+1}\geq a_{n}$. So, the sequence is ascending. 
The sequence is also bounded, because 
$$0<a_{n+1}=2 - \frac{3}{a_n+2}<2$$
Now, we have all the ingredients to conclude that the sequence is converging and the limits is $1$ from 
$$L=\frac{2L+1}{L+2} \Rightarrow L^2=1 \Rightarrow L=1$$
where $\lim\limits_{n\rightarrow \infty} a_n = L$ and since all $a_n \geq 0$ (thus $L$ can't be negarive).
A: You say:

Since $a_{2}\geq a_{1}$ then we assume that $a_{k}\geq a_{k+1}$

...and that assumption fails as soon as at $k=1$.
If the recurrence converges to some limit $L$, most probably $L$ is the fixed poind of the recurring function:
$$L=\frac{2L+1}{L+2}$$
This has two solutions, $L_1=-1$ and $L_2=1$.
Now use that hint to investigate the difference $a_n - L$.
Case 1.
Let $d_n = a_n - L_1 = a_n+1$. Then
$$\begin{align}d_{n+1} = a_{n+1}+1 & = \frac{2a_n+1}{a_n+2}+1 \\
& = \frac{2(a_n+1)-1}{(a_n+1)+1}+1 \\
& = \frac{2d_n-1}{d_n+1}+1 \\
& = \frac{3d_n}{d_n+1}
\end{align}$$
If $a_n$ was to approach $L_1$ then $d_n$ would have to converge to zero.
However, the denominator would then be approx. $1$, hence $d_{n+1} \approx 3d_n$ — the sequence gets repelled from $L_1$, not attracted to it; $L_1$ could be the limit point for $(a_n)$ sequence only if it was its first term (and then the sequence would be constant).
Case 2.
Let $e_n = a_n - L_2 = a_n-1$. Then
$$\begin{align}e_{n+1} = a_{n+1}-1 & = \frac{2a_n+1}{a_n+2}-1 \\
& = \frac{2(a_n-1)+3}{(a_n-1)+3}-1 \\
& = \frac{2e_n+3}{e_n+3}-1 \\
& = \frac{e_n}{e_n+3}
\end{align}$$
For $a_1=0$ we have $e_1=-1$ and for $-1\le e_n\lt 0$ we have $$\frac {e_n} 2\le e_{n+1} < 0$$ which implies $(e_n)$ tends to $0$ hence $(a_n)$ tends to $L_2 = 1$.
