2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.