1. ## Num. analysis #2

Hello. I'm having problem with these:

a). Prove that the Bisection algorithm gives a sequence that has the bound of error which converges linearly to zero.

b). The sequence $F_n$ described as $F_0$, $F_1$, and $F_{n+2}=F_n+F_{n+1}, n\geq0$, is called Fibonacci sequence and $x_n=\frac{F_{n+1}}{F_n}, \lim_{n\to\infty}{x_n}=x$ exists, prove that that limit is $x=\frac{(1+\sqrt5)}{2}$. (This number is called golden ratio)

2. Originally Posted by javax
Hello. I'm having problem with these:

a). Prove that the Bisection algorithm gives a sequence that has the bound of error which converges linearly to zero.
If the initial interval length is $L$, the interval length after $n$ itterations is

$L_n=\frac{L}{2^n}$

So:

$L_{n+1}=L_n/2$

and as $L_k$ is a bound on the error the convergence is linear.

CB

3. Originally Posted by javax
b). The sequence $F_n$ described as $F_0$, $F_1$, and $F_{n+2}=F_n+F_{n+1}, n\geq0$, is called Fibonacci sequence and $x_n=\frac{F_{n+1}}{F_n}, \lim_{n\to\infty}{x_n}=x$ exists, prove that that limit is $x=\frac{(1+\sqrt5)}{2}$. (This number is called golden ratio)

$
x_n=\frac{F_{n+1}}{F_n}=\frac{F_n+F_{n-1}}{F_n}=1+\frac{1}{x_{n-1}}
$

Now we are told that the limit as x \to \infty exists, so the limit must satisfy the equation:

$
x=1+\frac{1}{x}
$

which may be simplified to:

$x^2-x-1=0$

which has roots:

$
x=\frac{1\pm\sqrt{5}}{2}
$

Of these roots we may discard the one with the negative sign as $x$ must be greater than $0$ (in fact greater than $1$), so the required root is:

$
x=\frac{1+\sqrt{5}}{2}
$

CB