Reading guide · Proof index

Extreme and intermediate value theorems

Jiří Lebl, Basic Analysis I–II, version 6.3. Free author edition of this section. Selection and attribution · Notation.

L3.3.7: Complete bisection proof of a zero between strictly signed endpoints.

Proof.

We define two sequences {an}n=1∞\{ a_n \}_{n=1}^\infty and {bn}n=1∞\{ b_n \}_{n=1}^\infty inductively:
  1. Let a1≔aa_1 \coloneqq a and b1≔b.b_1 \coloneqq b\text{.}
  2. If f(an+bn2)≥0,f\left(\frac{a_n+b_n}{2}\right) \geq 0\text{,} let an+1≔ana_{n+1} \coloneqq a_n and bn+1≔an+bn2.b_{n+1} \coloneqq \frac{a_n+b_n}{2}\text{.}
  3. If f(an+bn2)<0,f\left(\frac{a_n+b_n}{2}\right) < 0\text{,} let an+1≔an+bn2a_{n+1} \coloneqq \frac{a_n+b_n}{2} and bn+1≔bn.b_{n+1} \coloneqq b_n\text{.}
Graph of a function that crosses the x-axis at c going upwards. The interval a sub 1 to b sub 1 is marked and f is negative at a sub 1 and positive at b sub 1. Next interval is a sub 2 which is equal to a sub 1 and b sub 2 is in the middle of the previous interval. Again the function is negative at a sub 2 and positive at b sub 2. We continue with the intervals with f being negative on the left and positive on the right. The next interval is from a sub 3 which equals a sub 2 and b sub 3 which is in the middle of the previous interval. For the next interval, a sub 4 is in the middle and b sub 4 is equal to b sub 3. The next a sub 5 is in the middle again and b sub 5 is equal to b sub 4. The number c is inside all of these intervals.
Figure 3.7. Finding roots (bisection method).
See Figure 3.7 for an example of the first five steps. If an<bn,a_n < b_n\text{,} then an<an+bn2<bn.a_n < \frac{a_n+b_n}{2} < b_n\text{.} So an+1<bn+1.a_{n+1} < b_{n+1}\text{.} As a1=a<b=b1,a_1 = a < b = b_1\text{,} induction gives that an<bna_n < b_n for all n.n\text{.} Furthermore, an≤an+1a_n \leq a_{n+1} and bn≥bn+1b_n \geq b_{n+1} for all n,n\text{,} that is, the sequences are monotone. As an<bn≤b1=ba_n < b_n \leq b_1 = b and bn>an≥a1=ab_n > a_n \geq a_1 = a for all n,n\text{,} the sequences are also bounded. Therefore, the sequences converge. Let c≔lim⁡n→∞anc \coloneqq \lim_{n\to\infty} a_n and d≔lim⁡n→∞bn,d \coloneqq \lim_{n\to\infty} b_n\text{,} where also a≤c≤d≤b.a \leq c \leq d \leq b\text{.} We need to show that c=d.c=d\text{.} Notice
bn+1−an+1=bn−an2.\begin{equation*} b_{n+1} - a_{n+1} = \frac{b_n-a_n}{2}. \end{equation*}
By induction,
bn−an=b1−a12n−1=21−n(b−a).\begin{equation*} b_n - a_n = \frac{b_1-a_1}{2^{n-1}} = 2^{1-n} (b-a) . \end{equation*}
As 21−n(b−a)2^{1-n}(b-a) converges to zero, we take the limit as nn goes to infinity to get
d−c=lim⁡n→∞(bn−an)=lim⁡n→∞21−n(b−a)=0.\begin{equation*} d-c = \lim_{n\to\infty} (b_n - a_n) = \lim_{n\to\infty} 2^{1-n} (b-a) = 0. \end{equation*}
In other words, c=d.c=d\text{.}
By construction, for all n,n\text{,}
f(an)<0andf(bn)≥0.\begin{equation*} f(a_n) < 0 \qquad \text{and} \qquad f(b_n) \geq 0 . \end{equation*}
Since lim⁡n→∞an=lim⁡n→∞bn=c\lim_{n\to\infty} a_n = \lim_{n\to\infty} b_n = c and ff is continuous at c,c\text{,} we may take limits in those inequalities:
f(c)=lim⁡n→∞f(an)≤0andf(c)=lim⁡n→∞f(bn)≥0.\begin{equation*} f(c) = \lim_{n\to\infty} f(a_n) \leq 0 \qquad \text{and} \qquad f(c) = \lim_{n\to\infty} f(b_n) \geq 0 . \end{equation*}
As f(c)≥0f(c) \geq 0 and f(c)≤0,f(c) \leq 0\text{,} we conclude f(c)=0.f(c) = 0\text{.} Thus also c≠ac \neq a and c≠b,c \neq b\text{,} so a<c<b.a < c < b\text{.}

L3.3.8: Both strict orientations of the intermediate value theorem.

Proof.

If f(a)<y<f(b),f(a) < y < f(b)\text{,} then define g(x)≔f(x)−y.g(x) \coloneqq f(x)-y\text{.} Then g(a)<0g(a) < 0 and g(b)>0,g(b) > 0\text{,} and we apply Lemma 3.3.7 to gg to find c.c\text{.} If g(c)=0,g(c) = 0\text{,} then f(c)=y.f(c) = y\text{.}
Similarly, if f(a)>y>f(b),f(a) > y > f(b)\text{,} then define g(x)≔y−f(x).g(x) \coloneqq y-f(x)\text{.} Again, g(a)<0g(a) < 0 and g(b)>0,g(b) > 0\text{,} and we apply Lemma 3.3.7 to find c.c\text{.} As before, if g(c)=0,g(c) = 0\text{,} then f(c)=y.f(c) = y\text{.}