A square root solving algorithm invented by my friend 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.
 A: 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$
A: 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
