# 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.

-
Please take a look at the latex corrections i made. Especially I am not sure about the last exponential. You wrote "^2^(n-1)", and I wrote "^(2(n-1))", if you mean "^(2^(n-1))" this has to be corrected. – k1next Feb 22 '13 at 10:39
thankyou @ZevChonoles, i will edit it :) – user62947 Feb 22 '13 at 10:39
@MJ96: Also take a look at how your LaTeX code has been edited; I encourage you to emulate it. You can find some good starting points on how to format mathematics on the site here. This AMS reference is very useful. If you need to format more advanced things, there are many excellent references on LaTeX on the internet, including StackExchange's own TeX.SE site. – Zev Chonoles Feb 22 '13 at 10:43
Second thing about your latex formatting. Avoid the following a$\gt0$, A$>$0 and use $a\gt0, \ A>0$. This is how the first is displayed a$\gt0$, A$>$0 and this the scond $a\gt0, \ A>0$ – k1next Feb 22 '13 at 10:44
Oh sorry, too late, I didn't see @ZevChonoles comment concerning Latex – k1next Feb 22 '13 at 10:45

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$.