I am making intro to numerical analysis exercises. One question is about the sequence $(\alpha_{n})$ of points that occur when applying it, a.k.a. the centers of the subsequent intervals, where the interval of the function is of the form $[a,b]$.
The exercise asks to use the following fact: $$|\alpha_{n}-\alpha_{n-1}|=(\frac{1}{2})^{n}(b-a)$$ to prove that, for $n>m$: $$|\alpha_{n}-\alpha_{m}|\leq (\frac{1}{2})^{n-m}$$ and to subsequently use this to show that $(\alpha_{n})$ is a Cauchy sequence.
I have been staring at this exercise for a while and can't wrap my head around it, I'm wondering if there might have been a typo. I don't understand how one can prove that it's Cauchy. I suppose you could, for small distances between $n$ and $m$ use the first equality and the second for if they are "far enough apart" (though the exercise only says to use the second inequality in your proof).
What's harder to me is the first part of the exercise, I thought you might find a proof by somehow showing that $$|\alpha_{n}-\alpha_{m}|=\frac{|\alpha_{n}-\alpha_{n-1}|}{|\alpha_{m}-\alpha_{m-1}|}$$ or $$|\alpha_{n}-\alpha_{m}|\leq\frac{|\alpha_{n}-\alpha_{n-1}|}{|\alpha_{m}-\alpha_{m-1}|}$$. I have tried using the triangle inequality or replacing $(b-a)$ by $|a_{n-1}-a_{n-2}|$ and continuing inductively (also even combining the last two methods), but could still not figure it out.
Lastly, the final part of the exercise asks to prove that the sequence converges to a root, and they show as a hint that in between each $\alpha_{n}$ and $\alpha_{n-1}$ is a root $\beta_{n}$. I think it's possible to not use the hint, and also I don't think the hint is true, as for example, $\alpha_{n-1}$ could be on the right side of a root and one places $\alpha_{n}$ next to the most recent $\alpha_{m}$ on the left side of the root, however $\alpha_{n}$ could then still be on the right side of the same root, with no root in between $\alpha_{n}$ and $\alpha_{n-1}$ (it would be great to get confirmation on this or why I'm wrong, in the meantime I think I know what they intended with it, that the upper bound is the same upper bound for each newly formed interval, where the root is in between either the left or right side of the interval).
Any help would be greatly appreciated. I like figuring out exercises on my own, so if I am on the right track that's enough for me to hear as well :) Thanks for any help in advance.
Though the way you stated the question itself is quite unclear, evidently you are talking about the Bisection method.
There are two issues here. The first is the inequality you are to prove. You are correct it is in error. It should be $$|\alpha_n - \alpha_m| \le \left(\frac 1{2^m} - \frac 1{2^n}\right)(b-a)$$
To see it, note that $$|\alpha_n - \alpha_m| = |(\alpha_n - \alpha_{n-1}) + (\alpha_{n-1} - \alpha_{n-2}) + \dots + (\alpha_{m+1} - \alpha_m)|\\ \le |\alpha_n - \alpha_{n-1}| + |\alpha_{n-1} - \alpha_{n-2}| + \dots + |\alpha_{m+1} - \alpha_m|$$
Can you see how to finish proving the inequality now? And can you see how to prove the sequence is Cauchy from this corrected inequality?
The second issue is your erroneous belief that the root could lie on one side of $\alpha_{n-1}$ and $\alpha_n$ could be on the other side. If this happens, then you have failed to properly follow the bijection method.
The Bijection method is used to approximate a root of a continuous function $f$. That is, to solve the equation $f(x) = 0$ for $x$. To start the method, you must find two values $a < b$ for which $f$ has opposite signs: Either $f(a) < 0 < f(b)$ or $f(b) < 0 < f(a)$. Once you have located two such values, you are guaranteed by the intermediate value theorem that there is root of $f$ in $[a,b]$. A continuous $f$ cannot travel from $f(a)$ to $f(b)$ without passing through the intermediate value of $0$.
Then you set $a_0 = a, b_0 = b$, and for each $n$, find the midpoint $\alpha_n = \frac{a_n + b_n}2$.
Assuming you do not get lucky and have the midpoint actually be the root, note that this results in
This forms a nested sequence of closed intervals: $$[a,b] = [a_0,b_0] \supset [a_1,b_1]\supset[a_2,b_2] \supset \dots$$ The $\{a_i\}$ are increasing and bounded above by $b$, while the $\{b_i\}$ are decreasing and bounded below by $a$. Thus the first sequence converges to its supremum while the second converges to its infimum. But since the lengths of the intervals converge to $0$, these two values must be the same limit $\alpha$. If $f(a) < 0$, then $f(a_i) < 0$ for all $i$, and by the continuity of $f, f(\alpha) = \lim_{i \to \infty}f(a_i) \le 0$. Similarly the $f(b_i) > 0$, so $f(\alpha) = \lim_{i \to \infty} f(b_i) \ge 0$, which means $f(\alpha) = 0$. The case when $f(a) > 0$ is similar.
So as long as you start with $f(a)$ and $f(b)$ of opposite signs, like you are required to do, and you replace endpoints per the instructions of the method, you are guaranteed to converge to a root.