Golden Iterations III

Calculus Level 5

See Original Golden Iterations I

and Original Golden Iterations II (updated)

You can find the value of ϕ = 1 + 5 2 \phi=\dfrac{1+\sqrt{5}}{2} by iteration. Sometimes, we want a faster algorithm.

In fact, we just need a way to find 5 \sqrt{5} !

Start with y 1 = 2 y_1=2 and y 2 = 1 2 ( y 1 + 5 y 1 ) = 2.25 y_2 =\frac{1}{2}\left(y_1+\frac{5}{y_1}\right)=2.25 and for the ( n + 1 ) (n+1) th iteration:

y n + 1 = 1 2 ( y n + 5 y n ) \large y_{n+1}=\frac{1}{2}\left(y_n+\frac{5}{y_n}\right) x n = 1 + y n 2 \large x_n = \frac{1+y_n}{2}

For large n n , we can express the error term as ∣ e n ∣ = ∣ x n − ϕ ∣ |e_n|=|x_n-\phi| . It can be shown that lim ⁡ n → ∞ ∣ e n + 1 ∣ ∣ e n ∣ c = a b \displaystyle \lim_{n\rightarrow\infty}\frac{|e_{n+1}|}{|e_n|^c}=\frac{a}{\sqrt{b}} , where a , b a, b are integers that do not have common divisors. Find a + b + c a+b+c .

Note: A few terms in the iteration seeded with y 1 = 2 y_1 = 2 or x 1 = 1.5 x_1=1.5 :

x 1 = 1.5 x_1=1.5

x 2 = 1.625000000000000 x_2=1.625000000000000

x 3 = 1.618055555555556 x_3=1.618055555555556

x 4 = 1.618033988957902 x_4=1.618033988957902

x 5 = 1.618033988749895 x_5=1.618033988749895

...


The answer is 8.

Max Yuen by Max Yuen , 42, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Mark Hennings
Jun 9, 2019

Note that y n + 1 − 5 = 1 2 y n ( y n − 5 ) 2 y_{n+1} - \sqrt{5} \; = \; \tfrac{1}{2y_n}(y_n - \sqrt{5})^2 from which is it easy to show that y n y_n converges to 5 \sqrt{5} . Note that e n = x n − φ = 1 2 ( y n − 5 ) e_n = x_n - \varphi = \tfrac12(y_n - \sqrt{5}) . Thus e n + 1 e n 2 = 2 ( y n + 1 − 5 ) ( y n − 5 ) 2 = 1 y n → 1 5 n → ∞ \frac{e_{n+1}}{e_n^2} \; = \; \frac{2(y_{n+1}-\sqrt{5})}{(y_n-\sqrt{5})^2} \; = \; \frac{1}{y_n} \; \to \; \frac{1}{\sqrt{5}} \hspace{2cm} n \to \infty making the answer 1 + 5 + 2 = 8 1+5+2=\boxed{8} .

0 Helpful 0 Interesting 3 Brilliant 0 Confused

Great example!

Max Yuen - 2 years ago
K T
Jun 7, 2019

e n = x n − φ = 1 2 ( y n − 5 ) e_n=x_n-φ= \frac{1}{2}(y_n -\sqrt{5})

e n + 1 = 1 2 ( y n + 1 − 5 ) = 1 2 ( 1 2 ( y n + 5 y n ) − 5 ) e_{n+1} = \frac{1}{2}(y_{n+1} -\sqrt{5}) = \frac{1}{2}( \frac{1}{2}(y_n+\frac{5}{y_n}) -\sqrt{5})

So e n + 1 e n c = 1 2 ( 1 2 ( y n + 5 y n ) − 5 ) ( 1 2 ( y n − 5 ) ) c \frac{e_{n+1} }{ e_n^c}=\frac{ \frac{1}{2}( \frac{1}{2}(y_n+\frac{5}{y_n}) -\sqrt{5})}{ (  \frac{1}{2}(y_n -\sqrt{5}))^c}

= 2 c − 2 y n + 5 y n − 2 5 ( y n − 5 ) c =2^{c-2} \frac{ y_n+\frac{5}{y_n} -2\sqrt{5}}{ (y_n -\sqrt{5})^c}

If we set f n = y n − 5 f_n=y_n-\sqrt{5} , this expression can be written as

= 2 c − 2 f n + 5 f n + 5 − 5 f n c =2^{c-2} \frac{ f_n+\frac{5}{f_n +\sqrt{5}} -\sqrt{5}}{ f_n^c}

= 2 c − 2 f n 2 f n c ( f n + 5 ) =2^{c-2} \frac{ f_n^2  }{ f_n^c (f_n+\sqrt{5})}

lim ⁡ n → ∞ e n + 1 e n c = lim ⁡ f → 0 2 c − 2 f n 2 f n c ( f n + 5 ) \lim_{n\to\infty}\frac{e_{n+1} }{ e_n^c}=\lim_{f\to0} 2^{c-2} \frac{ f_n^2  }{ f_n^c (f_n+\sqrt{5})} = lim ⁡ f → 0 2 c − 2 f 2 f c 5 = \lim_{f\to0} 2^{c-2} \frac{ f^2}{ f^c \sqrt{5}}

This limit has a nonzero value when c = 2 c=2 , and then evaluates to 1 5 \frac{ 1}{\sqrt{5}} .

a = 1 , b = 5 , c = 2 , a + b + c = 8 a=1, b=5, c=2, a+b+c=\boxed{8}

3 Helpful 0 Interesting 0 Brilliant 0 Confused
Max Yuen
Jun 9, 2019

There are many ways to solve this. Post your solutions!

The following is just one example:

Let f ( y ) = 1 2 ( y + 5 / y ) f(y) = \frac{1}{2}(y+5/y) . The algorithm is a fixed point iteration with y n + 1 = f ( y n ) y_{n+1}=f(y_n) and y ∗ = 5 y^*=\sqrt{5} is the fixed point.

We also notice that d f d y \frac{df}{dy} at y ∗ y^* is equal to 1 2 ( 1 − 5 ( y ∗ ) 2 ) = 0 \frac{1}{2}\left(1-\frac{5}{(y^*)^2}\right)=0 . Thus, for y n y_n 's near y ∗ y^* we can expand f ( y n ) f(y_n) as f ( y ∗ ) + 1 2 d 3 f d y 2 ( y ∗ ) ( y n − y ∗ ) 2 f(y^*) + \frac{1}{2}\frac{d^3f}{dy^2}(y^*)(y_n-y^*)^2 .

Thus,

f ( y n ) − f ( y ∗ ) = 1 2 d 2 f d y 2 ( y ∗ ) ( y n − y ∗ ) 2 f(y_n)-f(y^*) = \frac{1}{2}\frac{d^2f}{dy^2}(y^*)(y_n-y^*)^2

1 2 [ ( f ( y n ) − f ( y ∗ ) ] = d 2 f d y 2 ( y ∗ ) [ 1 2 ( y n − y ∗ ) ] 2 \frac{1}{2}\left[(f(y_n)-f(y^*)\right] = \frac{d^2f}{dy^2}(y^*)\left[\frac{1}{2}(y_n-y^*)\right]^2

We also note that

e n = x n − ϕ = 1 2 ( y n − y ∗ ) e_n = x_n-\phi=\frac{1}{2}(y_n-y^*)

and

e n + 1 = x n + 1 − ϕ = 1 2 ( y n + 1 − y ∗ ) = 1 2 ( f ( y n ) − f ( y ∗ ) ) e_{n+1} = x_{n+1}-\phi = \frac{1}{2}(y_{n+1}-y^*)=\frac{1}{2}(f(y_n)-f(y^*)) .

Thus, ∣ e n + 1 ∣ = ∣ d 2 f d y 2 ( y ∗ ) ∣ ∣ e n ∣ 2 |e_{n+1}| = |\frac{d^2f}{dy^2}(y^*)||e_n|^2 , and gives c = 2.

∣ d f d y ( y ∗ ) ∣ = 5 ( y ∗ ) 3 = 1 5 |\frac{df}{dy}(y^*)| = \frac{5}{(y^*)^3}=\frac{1}{\sqrt{5}}

Thus, we have for large n n

∣ e n + 1 ∣ ∣ e n ∣ 2 = 1 5 \large \frac{|e_{n+1}|}{|e_n|^2}=\frac{1}{\sqrt{5}}

so a = 1 , b = 5 , c = 2 a=1, b=5, c=2 and a + b + c = 8 a+b+c = 8

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...