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?

Solution 1:

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}$$

Solution 2:

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.