Let $c_n=\frac{1}{2}(a_n+b_n), r=\lim_{n\to \infty}c_n,$ and $e_n=r-c_n$. Here $[a_n,b_n]$, with $n\geq 0$, denotes the succesive intervals the arise in the bisection method when it is applied to a continuous function $f$.

(a) Show that for all $n$ and $m$, $a_m\leq b_n$

(b) Show that $r$ is the unique element in $\bigcap_{n=0}^{\infty}[a_n, b_n]$.

(c) Show that for all $n$, $[a_n, b_n]\supset [a_{n+1}, b_{n+1}].$

For (a), I'm a bit confused about how to solve this, I've thought about using induction in $n$ and $m$ but I do not know if it's the right way to solve this, could it be solved like this? How would the induction be done?

For (b), I know that because of Cantor's intersection toerema, we have $\bigcap_{n=0}^{\infty}[a_n, b_n]=\{r\}$, since $[a_{n+1}, b_{n+1}]\subset [a_n, b_n]$ and $[a_n,b_n]$ are compacts for all $n$ and $[a_n, b_n]\neq \phi$, but how do I prove that $f(r)=0$?

For (c), I know that for all $n$, we have that $a_n\leq a_{n+1}$ and $b_{n}\geq b_{n+1}$, with which $[a_{n+1}, b_{n+1}]\subset [a_n, b_n]$.

Is this argument correct? Thank you very much.


It seems easiest to me start with c). We assume that by bisection we mean that $a_0=a<b_0=b$, $f\left(a_0\right)f\left(b_0\right)\le0$ and from there we let $$c_n=\frac12\left(a_n+b_n\right)$$ And $$\left(a_{n+1},b_{n+1}\right)=\left\{\begin{array}{rl} \left(a_{n},c_{n}\right)&\text{if}\quad f\left(a_n\right)f\left(c_n\right)\le0\\ \left(c_{n},b_{n}\right)&\text{if}\quad f\left(a_n\right)f\left(c_n\right)>0\end{array}\right.$$ Then $$a_n=\frac12a_n+\frac12a_n<\frac12a_n+\frac12b_n=c_n<\frac12b_n+\frac12b_n=b_n$$ So if $f\left(a_n\right)f\left(c_n\right)\le0$ then $a_{n+1}=a_n<c_n=b_{n+1}<b_n$ and $f\left(a_{n+1}\right)f\left(b_{n+1}\right)=f\left(a_n\right)f\left(c_n\right)\le0$ and $b_{n+1}-a_{n+1}=c_n-a_n=\frac12\left(b_n-a_n\right)$.

Else if $f\left(a_n\right)f\left(c_n\right)>0$ then $a_n<a_{n+1}=c_n<b_n=b_{n+1}$ and $$f\left(a_{n+1}\right)f\left(b_{n+1}\right)=\left(\frac1{f\left(a_n\right)}\right)^2\left(f\left(a_n\right)f\left(c_n\right)\right)\left(f\left(a_n\right)f\left(b_n\right)\right)\le0$$ And $b_{n+1}-a_{n+1}=b_n-c_n=\frac12\left(b_n-a_n\right)$ So if the predicate that $a_n<b_n$ and $f\left(a_n\right)f\left(b_n\right)\le0$ is true for $n$, it is also true for $n+1$. Since it's true for $n=0$, it holds for all nonnegative integers $n$. Since $a_n\le a_{n+1}<b_{n+1}\le b_n$, $\left[a_{n+1},b_{n+1}\right]\subseteq\left[a_{n},b_{n}\right]$ and we have $\left[a_{n+1},b_{n+1}\right]\subset\left[a_{n},b_{n}\right]$ because $0<b_{n+1}-a_{n+1}<b_n-a_n$. So that establishes part c).

If $m\le n$ then $a_m\le a_n\le b_n$ else if $m>n$ then $a_m\le b_m\le b_n$, so we have part a).

We know that $\{a_n\}$ is a nondecreasing and bounded sequence so it has a limit $A$. Also $\{b_m\}$ is a nonincreasing and bounded sequence so it has a limit $B$. Since $b_{n+1}-a_{n+1}=\frac12\left(a_n-b_n\right)$ we have $$2^{n+1}\left(a_{n+1}-b_{n+1}\right)=2^{n}\left(a_n-b_n\right)=2^0\left(a_0-b_0\right)=b-a$$ So $$b_n-a_n=\frac{(b-a)}{2^n}$$ If $A<B$ then by the Archimedean property of the real numbers there is some $N$ such that $$\frac{(b-a)}{2^{n-1}}<B-A$$ So for $n\ge N$, $$b_n-a_n<\frac{B-A}2$$ Then $$\lim_{n\rightarrow\infty}\left(b_n-a_n\right)\le\frac{B-A}2$$ So $$0\le B-A\le\frac{B-A}2$$ Which contradicts the assumption that $B>A$ so it follows that $B=A=r$. Then, since also $a_n\le c_n\le b_n$ it follows by the squeeze theorem that $$\lim_{n\rightarrow\infty}c_n=r$$ If there were another element $$s\in\displaystyle{\bigcap_{n=0}^{\infty}}\left[a_n,b_n\right]$$ such that $s\ne r$, then we could find some $n$ such that $$\frac{b-a}{2^n}<|r-s|$$ So we can see that the set intersection isn't big enough to hold another element besides $r$. So that gets us to part b).

If $f\left(a_n\right)f\left(b_n\right)=0$ then either $f\left(a_n\right)=0$ or $f\left(b_n\right)=0$ so in either case there is some $x\in\left[a_n,b_n\right]$ such that $f\left(x\right)=0$. If $f\left(a_n\right)f\left(b_n\right)<0$ by the intermediate value theorem there must be some $x\in\left(a_n,b_n\right)$ such that $f\left(x\right)=0$. In any case for each interval $\left[a_n,b_n\right]$ there is some $x_n\in\left[a_n,b_n\right]$ such that $f(x)=0$. Since $r\in\left[a_n,b_n\right]$, for any $\epsilon>0$ by the continuity of $f$ there must be some $\delta(\epsilon)>0$ such that $\left|f(x)-f(r)\right|<\epsilon$ whenever $|x-r|<\delta(\epsilon)$. Choose $$N(\epsilon)=\frac{\ln\left(\frac{b-a}{\delta(\epsilon)}\right)}{\ln2}$$ Then $$|x_n-r|<\frac{b-a}{2^{N(\epsilon)}}\le\frac{b-a}{\frac{b-a}{\delta(\epsilon)}}=\delta(\epsilon)$$ So $|f(r)|=|0-f(r)|=|f(x_n)-f(r)|<\epsilon$ whenever $n>N(\epsilon)$, so $$\left|f(r)\right|=\lim_{n\rightarrow\infty}f(r)=0$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.