# Prove by Induction $\frac{a_n-\sqrt{A}}{a_n+\sqrt{A}} = \left[\frac{a_1-\sqrt{A}}{a_1+\sqrt{A}}\right]^{2^{n-1}}$

$a_1=\frac{1}{2}(a_0+\frac{A}{a_0})$;

$a_2=\frac{1}{2}(a_1+\frac{A}{a_1})$; and

$a_{n+1}=\frac{1}{2}(a_n+\frac{A}{a_n})$ for $n \geq 2$; where $a\gt 0$, $A\gt 0$.

Prove: $$\frac{a_n-\sqrt{A}}{a_n+\sqrt{A}} = \left[\frac{a_1-\sqrt{A}}{a_1+\sqrt{A}}\right]^{2^{n-1}}$$

Remarks:(This question i was doing for my exam tomorrow; and i just got stuck)

I have started with applying Second Principle of Mathematical Induction. I have never done this type of question earlier. Any help or hint will be appreciated.

Let us start: \begin{align} \frac{a_n -\sqrt{A}}{a_n+\sqrt{A}} &\underbrace{=}_{*} \frac{\frac{1}{2}a_{n-1}+ \frac{1}{2}\frac{A}{a_{n-1}} -\sqrt{A}}{\frac{1}{2}a_{n-1}+ \frac{1}{2}\frac{A}{a_{n-1}} +\sqrt{A}} \underbrace{=}_{**} \frac{\frac{1}{2}a_{n-1}^ 2+ \frac{1}{2}{A} -\sqrt{A}a_{n-1}}{\frac{1}{2}a_{n-1}^ 2+ \frac{1}{2}{A} +\sqrt{A}a_{n-1}} \\ &\underbrace{=}_{***} \frac{a_{n-1}^ 2+ {A} -2\sqrt{A}a_{n-1}}{a_{n-1}^ 2+ {A} +2\sqrt{A}a_{n-1}} =\frac{(a_{n-1}-\sqrt{A})^2}{(a_{n-1}+\sqrt{A})^2} \\ &=\Bigr(\frac{a_{n-1}-\sqrt{A}}{a_{n-1}+\sqrt{A}}\Bigl)^2\\ &\underbrace{=}_{****}\Bigr(\Bigl(\Bigl(\frac{a_{1}-\sqrt{A}}{a_{1}+\sqrt{A}}\Bigl)^2\Bigr)^2 \ldots \Bigr)^2\\ &= \Bigl(\frac{a_{1}-\sqrt{A}}{a_{1}+\sqrt{A}}\Bigl)^{2^{n-1}} \end{align} Here, I used the recurrence relation at $*$, multiplied enumerator and denominator with $a_{n-1}$ at $**$ and with 2 at $***$ and used induction at $****$.
Well first of all, note that the sequence $a_n$ converges towards $\sqrt{A}$. One possible derivation of the sequence is the application of Newton's method to a function that has a root at $\sqrt{A}$. This could be $f(x) = x^2-A$. Newtons's method then reads: \begin{align} x_{k+1} & = x_k -\frac{f(x_k)}{f'(x_k)} = x_k -\frac{x_k^2-A}{2x_k} =\frac{x_k^2+A}{2x_k}\\ &= \frac{1}{2} \Bigl(x_k+\frac{A}{x_k}\Bigr) \end{align} Which is exactly your sequence. So if we want to estimate $$\frac{a_n-\sqrt{A}}{a_n+\sqrt{A}}=c$$ where c is the value we derived from the prooved formula, we can use this information to find out, how good we approximate $\sqrt{A}$. \begin{align} &\frac{a_n-\sqrt{A}}{a_n+\sqrt{A}}=c \\ \Leftrightarrow&a_n-\sqrt{A} = c(a_n+\sqrt{A}) \\ \Leftrightarrow& a_n(1-c) = (1+c)\sqrt{A} \\ \Leftrightarrow& a_n= \frac{1+c}{1-c}\sqrt{A} \\ \end{align} So just by having a starting value $a_0$, we already know good solution $a_n$ will be, in sense of approximating $\sqrt{A}$. This means, that we can choose a $n$ a priori, for which $|a_n-\sqrt{A}|<\epsilon$, for a given $\epsilon$.