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?
Best Answer
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}$$