<s>[INST] Sequence of fractions that converges to $\sqrt{n}$ 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?
 [/INST] 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}$
</s>