# Math Club 2015-09-11

## 2273 days ago by calkin

A=plot(x^2-2, (x,0,3)) show(A)
B=plot(2*x-3,(x,0,3),color='red') show(A+B)
def newton_iterate(x): a=x/2+1/x return(a)
x0=1 xlist=[x0] N=10 for j in range(N): current_x = xlist[-1] new_x = current_x/2 + 1/current_x xlist.append(new_x) for appr in xlist: print appr
print sqrt(2.) for appr in xlist: print appr.n(),(appr -sqrt(2)).n(digits=14)
N = 20 a_list=[2,3] b_list=[1,2] for i in range(1,N): a=a_list[i] b=b_list[i] a_list.append(a^2 + 2*b^2) #b_list.append(2*a*b) #b_list = b_list + [2*a*b] b_list += [2*a*b]
for j in range(len(b_list)): print exp((log(b_list[j])/2^j).n())
for j in range(len(b_list)): print (b_list[j]/(1+sqrt(2))^(2^j)).n()
for i in range(10): print b_list[i], floor(sqrt(2)/4*(1+sqrt(2))^(2^i))
N = 15 a_list= b_list= for i in range(N): a=a_list[i] b=b_list[i] a_list.append(a^2 + 4*b^2) #b_list.append(2*a*b) #b_list = b_list + [2*a*b] b_list += [2*a*b]
for j in range(5): print j, a_list[j],b_list[j]

## Continuing our investigations into the approximations using Newton's method of $\sqrt{4}$.

Starting with $x_0=1$, $x_1=5/2$, and

$x_{n+1} = \frac{x_n}{2} + \frac{2}{x_n}$

we can write

$x_n = \frac{a_n}{b_n}$

in which $a_n, b_n$ are integers with no common factors.  Then

$\frac{a_{n+1}}{b_{n+1}} = \frac{a_n}{2b_n} + \frac{2b_n}{a_n} = \frac{a_n^2 + 4 b_n^2}{2a_nb_n}$

Now, for $n\geq 1$, we have $a_n$ is odd  and $b_n$ is even, so $a_n^2+ 4b_n^2$ is odd.  Furthermore, any odd prime divisor of $2a_nb_n$ must {\em fail} to divide $a_n^2 + 4b_n^2$, since $a_n$ and $b_n$ have no common factors.

Hence

$a_{n+1} = a_n^2 + 4b_n^2 \mbox{ and } b_{n+1} = 2a_nb_n .$

## Proving that $an-2b_n =1$.

We'll prove this by induction.  Suppose that $a_n - 2b_n=1$.  Then

$a_{n+1} - 2 b_{n+1} = (a_n^2 + 4 b_n^2) -2 (2a_nb_n)$

$= (a_n^2 + 4 b_n^2) - 2(4 a_n b_n)$

$= a_n^2- 4 a_nb_n + 4 b_n^2 = (a_n-2b_n)^2 = 1^2 = 1$

## How big is $x_n - 2$?

$x_n-2 = \frac{a_n}{b_n} - 2 = \frac{a_n -2b_n }{b_n} = \frac{1}{b_n}.$