Sequence of fractions that converges to $\sqrt{n}$

Question

Begin with any two positive integers $a,b$. Let

$$s_1 = \frac{a}{b}$$

and recursively we define $s_{i+1}$ from $s_i$ as follows: If ${s_i}$ is the fraction $\frac{a'}{b'}$, then set

$$s_{i+1} = \frac{a'+2b'}{a'+b'}$$

(Notice that the actual value of the $s_{i+1}$ does not depend on the exact way we choose to represent $s_i$ in fractions)

How do we show that $s_i \to \sqrt{2}$ as $i\to \infty$?

In general, sending $\frac{a'}{b'}$ to $\frac{a'+nb'}{a'+b'}$ supposedly leads to $s_i \to \sqrt{n}$. How might we prove this?

Answer 1

In the general case dividing by $b'$ in the nominator and the denominator we have that:

$$s_{i+1} = \frac{s_i + n}{s_i + 1}$$

Now consider two cases, namely $s_i \le \sqrt{n}$ and $s_i > \sqrt{n}$. Now let WLOG $s_i \le \sqrt{n}$. Then expressing $s_{i+2}$ by $s_i$ we have that:

$$s_{i+2} = \frac{s_{i+1} + n}{s_{i+1} + 1} = \frac{\frac{s_i + n}{s_i + 1} + n}{\frac{s_i + n}{s_i + 1} + 1} = \frac{(n+1)s_i + 2n}{2s_i + (n+1)}$$

From this we have that $s_{i+2} \ge s_i \iff (n+1)s_i + 2n \ge 2s_i^2 + (n+1)s_i \iff n \ge s_i^2$, which is true. Also we have that $s_{i+2} \le \sqrt{n} \iff ((n+1) - 2\sqrt{n})s_i \le \sqrt{n}(n+1) - 2n$, but this is true as: $((n+1) - 2\sqrt{n})s_i \le ((n+1) - 2\sqrt{n})\sqrt{n} = \sqrt{n}(n+1) - 2n$. Therefore if $i$ is odd/even we have that the sequence of odd/even indexes is convergent. Let WLOG $i$ be odd, then we can write $\lim_{n \to \infty} s_{2i} = L$. Taking the limit from the previous equation we have:

$$L = \frac{(n+1)L + 2n}{2L + (n+1)} \iff 2L^2 + (n+1)L = (n+1)L + 2n \iff L = \sqrt{n}$$

Similarly we can prove the case when $s_i > \sqrt{n}$ and also that the subsequence with indexes of other parity is convergent to $\sqrt{n}$.

Finaly as both $s_{2i}$ and $s_{2i+1}$ converge to $\sqrt{n}$ we can conclude that $s_i$ converges to $\sqrt{n}$

Answer 2

Let $t_i$ denote the top part of the fraction and $\ell_i$ the bottom part. Then $t_0 = a$, $\ell_0 = b$ and $$ \begin{pmatrix} t_{i+1} \\ \ell_{i+1} \end{pmatrix} = \begin{pmatrix} 1 & n \\ 1 & 1 \end{pmatrix}\begin{pmatrix} t_{i} \\ \ell_{i} \end{pmatrix}. $$ You can then diagonalize the middle matrix $$ \begin{pmatrix} 1 & n \\ 1 & 1 \end{pmatrix} = P^{-1}DP. $$ It then follows that \begin{align} \begin{pmatrix} t_{i} \\ \ell_{i} \end{pmatrix} &= P^{-1}D^iP\begin{pmatrix} t_{0} \\ \ell_{0} \end{pmatrix} = P^{-1}\begin{pmatrix} d_{1}^{i} & 0 \\ 0 & d_{2}^{i} \end{pmatrix}P\begin{pmatrix} a \\ b \end{pmatrix}. \end{align}

Answer 3

One thing you could do would be to see whether $s_i^2$ converges to $2$. We do this by comparing $|s_i^2 - 2|$ and $|s_{i+1}^2 - 2|$: $$ \begin{align} \left|\frac{a'^2 - 2b'^2}{b'^2}\right| \quad &\text{versus} \quad \left|\frac{a'^2 + 4a'b' + 4b'^2 - 2a'^2 - 4a'b' - 2b'^2}{a'^2 + 2a'b' + b'^2}\right|\\ \left|\frac{a'^2 - 2b'^2}{b'^2}\right| \quad &\text{versus} \quad \left|\frac{2b'^2 - a'^2 }{a'^2 + 2a'b' + b'^2}\right| \end{align} $$ and we see that the two numerators are negatives of one another, which doesn't affect our result, while the denominator on the right is larger (since we assumed $a', b' > 0$). So the right fraction is smaller.

Also note, that for $i \geq 2$, we have $s_i \geq 1$. That means that of the two above fractions, the magnitude of the right one is a quarter (or less) of the magnitude of the left one, since $a' \geq b'$.

In other words, $|s_{i+1}^2 - 2| \leq \frac 14 |s_i^2 - 2|$, so the sequence $s_i^2$ clearly converges to $2$. This means that $\sqrt{s_i^2} = s_i$ converges to $\sqrt 2$.