On a recursive sequence exercise. I have the following recursive sequence of which I want to prove the convergence:
$$x_{n+1} = \frac{x_n +1}{x_n +2 }$$ and $x_1 = 0$
I have proved that it is bounded above by $1$ and that it is increasing by taking the derivative, but I am told to do it without using derivatives.
How could I show that it's bounded and increasing using only elementary methods?
In particular I would like to prove that it is bounded by $\frac{\sqrt{5} - 1}{2}$ (this is the limit), but any additional ways to solve it are obviously very appreciated.
 A: BOUNDED: $$x_{n+1}=\frac{x_n+1}{x_n+2}=1-\frac{1}{x_n+2}<1 \, \forall \, n \in \mathbb{N}$$
Hence $\{x_n\}$ is bounded above by $1$.
MONOTONIC NATURE:
Say $P(n):x_{n+1}>x_n \, \forall \, n \in \mathbb{N}$  be the induction statement.
For $n=1$, $x_2=\frac{1}{2}>0=x_1$
So $P(1)$ is true.
Assume $P(n)$ is true for some $k$, $k \in \mathbb{N}$.
So we get $$x_{k+1}>x_k$$ or $$x_{k+1}+2>x_{k}+2$$ or $$\frac{1}{x_{k+1}+2}<\frac{1}{x_{k}+2}$$ or $$-\frac{1}{x_{k+1}+2}>-\frac{1}{x_{k}+2}$$ or $$1-\frac{1}{x_{k+1}+2}>1-\frac{1}{x_{k}+2}$$ or $$\frac{x_{k+1}+1}{x_{k+1}+2}>\frac{x_{k}+1}{x_{k}+2}$$ or $$x_{k+2}>x_{k+1}$$
Hence $P(n)$ is true by mathematical induction.
LIMIT: Say $\lim_{n\to\infty} x_n = l$
$$l=\frac{l+1}{l+2}$$ or $$l^2+2l=l+1$$ or $$l^2+l-1 \Rightarrow l= \frac{1+\sqrt{5}}{2}$$
A: Often, when a sequence $x_n$ has a limit $a$, it's interesting to study $u_n=x_n-a$ instead. Here we will take $u_n=a-x_n$, but it's the same idea. Of course, we don't know in advance that $a$ is the limit, it's just a guess.
Let $a=\frac{\sqrt{5}-1}{2}$, and $u_n=a-x_n$.
Notice that $a^2=1-a$, and that $x_n\geq0$.
We would like to prove that $u_n$ is positive and decreasing, and tends to $0$.
$$u_{n+1}=a-x_{n+1}=a-\frac{a-u_n+1}{a-u_n+2}$$
$$u_{n+1}=\frac{a^2-au_n+2a-a+u_n-1}{x_n+2}=\frac{u_n(1-a)+a^2+a-1}{x_n+2}$$
$$u_{n+1}=u_n\frac{(1-a)}{x_n+2}$$
And since $0<\dfrac{1-a}{x_n+2}\leq\dfrac{1-a}{2}<1$, you have that if $u_n>0$, then $u_{n+1}>0$ as well, thus $u_n>0$ for all $n$ (since $u_1=a>0$).
Also, $u_{n+1}<u_n\dfrac{1-a}{2}<u_n$, and the sequence $u_n$ is decreasing (thus $x_n$ is increasing).
Finally, 
$$0<u_n<u_1\left(\frac{1-a}{2}\right)^{n-1}\underset{n\to\infty}{\longrightarrow}0$$
Hence $u_n\to0$ and $x_n\to a$.

A note about the initial "guess" $a=\frac{\sqrt{5}-1}{2}$. When you are given a sequence $u_{n+1}=f(u_n)$ with a continuous function $f$, then if $u_n$ has a limit, it must be a solution of the equation $L=f(L)$. Thus you can find the possible candidates for a limit. Here the equation is
$$L=\frac{1+L}{2+L}$$
$$L^2+L-1=0$$
And you find that it has solutions $\dfrac{-1\pm\sqrt{5}}{2}$, one of which is negative, thus not a good candidate since $x_n\geq0$. The other is our $a$.
If $x_n$ has a limit, it's thus $a$. The purpose of the first part of the answer is to prove that $x_n$ is indeed convergent. Actually, once you know $u_n$ is positive and decreasing, you know it's convergent (see here), thus also $x_n$. I added a more direct proof since it's easy here, and it gives you also the rate of convergence.
A: Functions of the form $f:\; x \mapsto \dfrac{ax+b}{cx+d}$ are fractional linear transformations, and their iterates can be computed in closed form: 
$f^n: x \mapsto \dfrac{a_n x + b_n}{c_n x + d_n}$ where the matrix
$\pmatrix{a_n & b_n\cr c_n & d_n} = \pmatrix{a & b\cr c & d\cr}^n$.
In your case $$\pmatrix{a & b\cr c & d\cr} = \pmatrix{1 & 1\cr 1 & 2\cr}$$
and it's not hard to show that $$\pmatrix{a_n & b_n\cr c_n & d_n\cr} = \pmatrix{F_{2n-1} & F_{2n}\cr F_{2n} & F_{2n+1}}$$ where $F_n$ are the Fibonacci numbers.  In particular, with $\phi = \dfrac{1+\sqrt{5}}{2}$ is the "golden ratio", we have $F_n \sim \phi^n$ as $n \to \infty$.  With 
 $x_1 = 1$ we get $$x_n = f^{n-1}(1) = \dfrac{F_{2n-3} + F_{2n-2}}{F_{2n-2} + F_{2n-1}} = \dfrac{F_{2n-1}}{F_{2n}} \to 1/\phi = \dfrac{-1+\sqrt{5}}{2}$$
A: represent your sequence as points $(x_n,1)$ on the projective line.
then
$$
(x_{n+1},1) = (x_{n},1)\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}
$$
let $\bar v$ be any element of the projective line. then it is easy to show
$$
\bar v\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}^n = \bar v\begin{bmatrix} f_n & f_{n+1} \\  f_{n+1} &  f_{n+2} \end{bmatrix} = \bar v\begin{bmatrix} \frac{f_n}{f_{n+1}} & 1 \\  1 &  \frac{f_{n+2}}{f_{n+1}} \end{bmatrix} \to \bar v\begin{bmatrix} \theta^{-1} & 1 \\  1 & \theta \end{bmatrix}
$$
where $\theta$ is the golden ratio. substituting $(1,1)$ for the first term the limit is seen to be:
$$
\frac{\theta^{-1}+1}{1+\theta} = \frac1{\theta}
$$
