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

-
Since you are new, I want to give some advice about the site: To get the best possible answers, you should explain what your thoughts on the problem are so far. That way, people won't tell you things you already know, and they can write answers at an appropriate level; also, people tend to be more willing to help you if you show that you've tried the problem yourself. If this is homework, please add the [homework] tag; people will still help, so don't worry. Also, many would consider your post rude because it is a command ("Prove"), not a request for help, so please consider rewriting it. –  Zev Chonoles Feb 22 '13 at 10:38
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. –  sonystarmap Feb 22 '13 at 10:39
Polite version: Welcome to math.SE! Since you are new, go reading the FAQs and guidelines, specifically about the purpose of the site and the proper way of asking questions. Not so polite version: This is not a question. Show us your partial progress and ask something specific. Also, if this is homework, tag it properly. –  Andrea Orta Feb 22 '13 at 10:40
@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$ –  sonystarmap Feb 22 '13 at 10:44
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$.