Recurrence relation in the bisection method

Question

When beginning to talk about error bounds on the bisection method for root finding, my book states the following:

Let $a_n$ $b_n$ and $c_n$ denote the $n$th computed values of $a,b,$ and $c$, respectively. Then easily we get $$ b_{n+1}-a_{n+1}=\frac{1}{2}(b_{n}-a_{n}),\ n\ge1 $$ and it is straightforward to deduce that $$ b_{n}-a_{n}=\frac{1}{2^{n-1}}(b-a),\ n\ge1 $$ where $b-a$ denotes the length of the original interval with which we started.

However, wouldn't it be $b_{n}-a_{n}=\frac{1}{2^{n}}(b-a)$ instead? Simply take $n=1$. As stated, it wouldn't make sense that $b_{1}-a_{1}=(b-a)$, would it?

Answer 1

Informal statements on sequences are often a little ambiguous.

Sometimes a sequence is thought of as $a_0,a_1,a_2,\cdots$, sometimes as $a_1,a_2,a_3,\cdots$, and when you speak of the $n^{th}$ term, that can be $a_{n-1}$ or $a_n$. Here it is clear that numbering starts at $1$.

But another source of ambiguity is in "computed values". Shall we consider that the very first $a,b$ are computed, or are just given ? In the first situation, $a_1=a$. In the second, $a_1$ is a later value (as if $a=a_0$).

---

What we can say for sure: if we start with an interval of length $b-a$ before any iteration, every iteration halves that length and after $n$ iterations, it becomes $\dfrac{b-a}{2^n}$.

Answer 2

$$a_{n+1}-b_{n+1}=\frac{1}{2}(a_n-b_n) \implies f_{n+1}=\frac{1}{2}f_n$$ One may do multiplicative teslescoping as $$f_1=\frac{1}{2} f_0$$ $$f_2=\frac{1}{2} f_1$$ $$f_3=\frac{1}{2} f_2$$ $$........$$ $$........$$ $$f_{n-1}=\frac{1}{2} f_{n-2}$$ $$f_n=\frac{1}{2} f_{n-1}$$ Multiplying them, we get $$\implies f_n=\frac{1}{2^n} f_0, f_0=(a_0-b_0),$$ where $a_0-b_0$ needs to de given.