Nth root

We first study the sequence $$x_{n+1}=\dfrac{1}{2}(x_n+\dfrac{a}{x_n}),$$ where $a=2,x_1=1$ and examine the numbers $x_2,x_3,x_4,x_5$ : $$x_2=\dfrac{1}{2}(1+2)=1.5\\x_3=\dfrac{1}{2}(1.5+\dfrac{2}{1.5})\approx 1.4167\\x_4=\dfrac{1}{2}(1.4167+\dfrac{2}{1.4167})\approx1.4142\\x_5=\dfrac{1}{2}(1.4142+\dfrac{2}{1.4142})\approx 1.4142\\ \cdots$$ We can show that the sequence tends to $\sqrt{2}$. More generally, take $l=\lim x_n$, so $l=\lim x_{n+1}$ and so $$\begin{align*}l&=\dfrac{1}{2}(l+\dfrac{a}{l})\\ 2l^2&=l^2+a\\ l&=\sqrt{a}\;\;\text{(reject the negative number because }\;x_n>0).\end{align*}$$ This sequence helps us generate the square root of any positive number. You may ask: how can we come up with such a sequence? The reasoning is as follows: if $x_1\neq \sqrt{a}$, then we have $x_1<\sqrt{a}$ or $x_1>\sqrt{a}$. In the first case, we have $\sqrt{a} x_1<a$ or $\sqrt{a}<\dfrac{a}{x_1}$. In the other case, if $x_1>\sqrt{a}$, then $\sqrt{a}>\dfrac{a}{x_1}$. Therefore, we have $x_1<\sqrt{a}<\dfrac{a}{x_1}$ or $\dfrac{a}{x_1}<\sqrt{a}<x_1$. If we take the average of $x_1$ and $\dfrac{a}{x_1}$, namely $x_2=\dfrac{1}{2}(x_1+\dfrac{a}{x_1})$, then the result will be between $x_1$ and $\dfrac{a}{x_1}$. Repeat this process several times: $$x_3=\dfrac{1}{2}(x_2+\dfrac{a}{x_2}), x_4=\dfrac{1}{2}(x_3+\dfrac{a}{x_3}) \cdots$$ The sequence $(x_n)$ tends to $\sqrt{a}$.

In fact, the sequence for square root can be generalised to one for nth root. $x_{n+1}=\dfrac{1}{p}\bigg((p-1)x_n+\dfrac{a}{x_n^{p-1}}\bigg)$ The reasoning is similar. We consider $\underbrace{x_n\times x_n\times \cdots\times x_n}_{p-1\; times}\times \dfrac{a}{x_n^{p-1}}=a$ and take the average of these $p$ factors.

These sequences are related to the method of Newton-Raphson. Finding the square root is equivalent to solving the equation $x^2-a=0$. Let $f(x)=x^2-a$. Then, $$x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}=x_n-\dfrac{x_n^2-a}{2x_n}=\dfrac{1}{2}(x_n+\dfrac{a}{x_n}).$$ As for the nth root, we can solve the equation $x^p-a=0$ and we have $$x_{n+1}=x_n-\dfrac{x_n^p-a}{px_n^{p-1}}=x_n-\dfrac{1}{p}x_n+\dfrac{a}{px_n^{p-1}}=\dfrac{1}{p}\bigg((p-1)x_n+\dfrac{a}{x_n^{p-1}}\bigg).$$