Convergents of square root of 2 On wikipedia I read about the continued fraction of the square root of 2:
$$1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{...}}}}$$
The first convergents are $\frac{1}{1},\frac{3}{2},\frac{7}{5},\frac{17}{12},\frac{41}{29}$.
They say that if $\frac{p}{q}$ is one convergent, $\frac{p+2q}{p+q}$ will be the next.
This seems to be right, but is there a proof for it.
There also seems to be a recursive formula for the numerator and the denominator:
$a(n) = 2a(n-1) + a(n-2)$: the numerator is twice the last numerator plus the numerator before that one.
It's the same for the denominator, but with different starting values.
So is there a proof for these formulas?
 A: Suppose one convergent is $\frac pq$
The key is to see that the next convergent can be written as $$1+\frac 1{1+\frac pq}=1+\frac  q{p+q}=\frac {p+2q}{p+q}$$
Now we can set $p_n=p_{n-1}+2q_{n-1}$ and $q_n=p_{n-1}+q_{n-1}$ so that $p_{n-1}=q_n-q_{n-1}$ which means 
$$p_n-p_{n-1}=(p_{n-1}+2q_{n-1})-(p_{n-2}+2q_{n-2})=p_{n-1}-p_{n-2}+2p_{n-2}$$
ie$$p_n=2p_{n-1}+p_{n-2}$$
A: There's an algorithm for finding continued fractions. For $x\in\mathbb R$, take $\lfloor x\rfloor$, and if $x$ wasn't an integer, continue with $\frac1{x-\lfloor x\rfloor}$.
In your case $\lfloor\sqrt2\rfloor=1$ and $\frac1{\sqrt2-1}=\sqrt2+1$. Then $\lfloor\sqrt2+1\rfloor=2$, so we again have $\frac1{\sqrt2-1}$.
So the continued fraction is
$$[1;2,2,\ldots]=1+\frac{1}{2+\frac{1}{2+\frac{1}{\ldots}}}$$
You can find the recursive formula for convergents (in this case $[1],[1;2],[1;2,2],\ldots$) in the "useful theorems" section on Wikipedia.
These theorems are indeed very useful and answer any question you could have about these fractions.
