Convergence of an oscillating recursive sequence Define the recursive sequence 
$ q_{n+1} = \dfrac{q_n+2}{q_n+1};\;q_0=1 $
If we knew that 
$ q_n \to q;\;n\to \infty $
then it's easy to show what follows
$ q_{n+1}\left(q_n+1\right) = q_n+2 $
$ q_{n+1}\cdot q_n+q_{n+1}-q{n}=2 $
$ q^2 = 2 \rightarrow q = \sqrt 2;\;n\to\infty $ 
I don't know how to prove that $q_n$ converges.
The sequence is oscillating and I know, empirically, that the sequence
$a_n=q_n-q_{n+1}$
is an alternate sequence whose general term goes to zero, thus $a_n$ converges.
Any help will be greatly appreciated, thank you.
 A: It is convenient to represent every $q_n$ as a reduced fraction $\frac{a_n}{b_n}$. So $a_0=b_0=1$ and:
$$ \frac{a_{n+1}}{b_{n+1}} = \frac{\frac{a_n}{b_n}+2}{\frac{a_n}{b_n}+1}=\frac{a_n+2 b_n}{a_n+b_n}\tag{1}$$
or:
$$ \left(\begin{array}{c}a_{n+1}\\b_{n+1}\end{array}\right)=\left(\begin{array}{cc}1 & 2\\ 1 & 1\end{array}\right)\left(\begin{array}{c}a_{n}\\b_{n}\end{array}\right).\tag{2}$$
The eigenvalues of such a matrix are $1\pm\sqrt{2}$ and the eigenvectors are $ \left(\begin{array}{c}\pm\sqrt{2}\\1\end{array}\right)$.
Since $a_n,b_n>0$, $\lim_{n\to +\infty}\frac{a_n}{b_n}=\sqrt{2}$ follows.
A: Your series, when written as a sequence of fractions, is:
$1, \frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29}...$
Notice that the denominator of term $n + 1$ is the sum of the denominator and numerator of term $n$, and the numerator of term $n + 1$ is twice the denominator of term $n$ plus its numerator.
So let's write two sequences, denominator $D(n)$ and numerator $N(n)$, mutually recursive:
$D(n + 1) = D(n) + N(n)$ and $N(n + 1) = 2D(n) + N(n)$ with $D(0) = N(0) = 1$
Now we just need to show that $q_n = \frac{N(n)}{D(n)}$. Well, it's true for the base case of $n = 0$. Then for the inductive case, well, we have your recurrence $q_{n + 1} = \frac{q_n + 2}{q_n + 1}$, and by inductive hypothesis: $q_{n + 1} = \frac{\frac{N(n)}{D(n)} + 2}{\frac{N(n)}{D(n)} + 1} = \frac{N(n) + 2D(n)}{N(n) + D(n)} = \frac{N(n + 1)}{D(n + 1)}$ as required.
Now, we can generate yet another recurrence. Recall $q_n = N(n)/D(n)$. Then we can show:
$q_{n + 1} = 1 + \frac{1}{1 + q_n}$
Here is why:
$q_{n + 1} = \frac{N(n) + 2D(n)}{N(n) + D(n)} = 1 + \frac{D(n)}{N(n) + D(n)} = 1 + \frac{1}{\frac{N(n) + D(n)}{D(n)}} = 1 + \frac{1}{1 + \frac{N(n)}{D(n)}} = 1 + \frac{1}{1 + q_n}$
Now you might notice the similarity to the continued fraction expansion of $\sqrt{2}$. Continued Fraction of root 2
To show convergence, we define the error term $e(n) = q_n - \sqrt{2}$ and show that the absolute value of this error term decreases faster than geometrically with $n$, which in turn shows that it converges to $0$. Start with our latest recurrence:
$q_{n + 1} = 1 + \frac{1}{1 + q_n}$ so
$\sqrt{2} - e(n + 1) = 1 + \frac{1}{1 + \sqrt{2} - e(n)}$
$(\sqrt{2} - e(n + 1))(1 + \sqrt{2} - e(n)) = 2 + \sqrt{2} - e(n)$
$\sqrt{2} + 2 - \sqrt{2}e(n) - e(n + 1)(1 + \sqrt{2} - e(n)) = 2 + \sqrt{2} - e(n)$
$\sqrt{2}e(n) + e(n + 1)(1 + \sqrt{2} - e(n)) = e(n)$
$e(n + 1)(1 + \sqrt{2} - e(n)) = e(n)(1 - \sqrt{2})$
$e(n + 1) = e(n)\frac{(1 - \sqrt{2})}{(1 + \sqrt{2} - e(n))}$
Now, since $f(0) = 1$, then $|e(0)| < 1$. Assuming then that $|e(n)| < 1$
we can show that $|\frac{(1 - \sqrt{2})}{(1 + \sqrt{2} - e(n))}| < \frac{\sqrt{2} - 1}{\sqrt{2}} < 1$. Proceed as follows.
$|e(n)| < 1$ so
$1-e(n) > 0$
$1 + \sqrt{2} - e(n) > \sqrt{2}$
$|\frac{(1 - \sqrt{2})}{(1 + \sqrt{2} - e(n))}| < \frac{\sqrt{2} - 1}{\sqrt{2}} < 1$
And the convergence is shown.
