A square root solving algorithm invented by my friend

Question

Recently, my friend told me a square root algorithm:

$$ \left\{ \begin{array}{lll} p_{n+1}&=&p_n+aq_n \\ q_{n+1}&=&p_n+q_n\end{array}\right.$$

Finally, $p_n/q_n$ is near $\sqrt{a}$.

But I'm not quite understand this method, we can rewrite the expression like this $$ \frac{p_{n+1}}{q_{n+1}}=\frac{p_n}{p_n+q_n}+a\frac{q_n}{p_n+q_n}$$ and it just looks like the mean value formula $$ \lambda+(1-\lambda)a$$ I don't know how it works and how to understand it intuitively.

Answer 1

Actually, it's not a new stuff.

$p_{n},q_{n}$ are the convergents of continued fraction expression for $\sqrt{a}$

\begin{align*} \displaystyle \sqrt{a} &= 1+\frac{a-1}{1+\sqrt{a}} \\ &=1+\frac{a-1}{\displaystyle 2+\frac{a-1}{1+\sqrt{a}}} \\ &=1+\frac{a-1} {2+\displaystyle \frac{a-1} {2+\displaystyle \frac{a-1}{2+\ddots}}} \\ \frac{p_{n}}{q_{n}} &= 1+\frac{a-1}{1+\displaystyle \frac{p_{n-1}}{q_{n-1}}} \\[5pt] \frac{p_{n}}{q_{n}} &=\frac{p_{n-1}+a q_{n-1}}{p_{n-1}+q_{n-1}} \\ \end{align*}

Note that for $\sqrt{a}\notin \mathbb{Q}$ with $\gcd(p_{n},q_{n})=1 \implies \gcd(p_{n}+a q_{n},p_{n}+q_{n})=1$

Answer 2

Denote $x_n = p_n / q_n$.

You have found that:
$$ \frac{p_{n+1}}{q_{n+1}}=\frac{p_n}{p_n+q_n}+a\cdot\frac{q_n}{p_n+q_n}$$

So:
$$ \frac{p_{n+1}}{q_{n+1}}=\frac{1}{1+q_n/p_n}+a\cdot\frac{1}{p_n/q_n+1}$$
$$ x_{n+1}=\frac{1}{1+1/x_n}+a\cdot\frac{1}{x_n+1}$$
$$ x_{n+1}=\frac{x_n}{x_n+1}+a\cdot\frac{1}{x_n+1}$$
$$ x_{n+1}=\frac{x_n+a}{x_n+1}$$

Now denote the limit of $x_n$ by $L$.
You get from the last equation that:
$L^2 + L = a+L$.

All you have to do is to prove that the sequance $x_n$ indeed has a limit.
I think this can be proved by showing that it's monotonous (from a certain point on) and it's limited.

This seems like a well-known method to me.
Reminds me of Newton's method, not sure if it's 100% the same though.

Newton's method