Let $f,g$ be continuous functions on $[a,b]$ with $f(a) \geq g(a)$ and $f(b) \leq g(b)$. Prove there is some $x$ in $[a,b]$ where $f(x)=g(x)$.
My question is about my following method and not others (for example, using IVT on h=f-g).
Define $f$ crosses $g$ on $[m,n]$ if $f(a) \geq g(a)$ and $f(b) \leq g(b)$ OR $f(a) \leq g(a)$ and $f(b) \geq g(b)$. And let $I_k = [m_k, n_k]$ with $I_0 = [a,b]$.
If $f(x) = g(x)$ for $x=m_0, n_0, (m_0+n_0)/2$. Then we are done. Otherwise let $d=(m_0+n_0)/2$. Since $f,g$ crosses on $I_0$ and either $f(d) > g(d)$ or $f(d) < g(d)$, then either $f,g$ cross on $[m_0,d]$ or $[d,n_0]$. Let $I_1$ be that interval, and repeat this process.
If this process terminates, then we have found an $x$ where $f=g$. Otherwise, since $m_k$ is a monotonic increasing sequence bounded above by $b$, it converges to some limit $x_0$. Since $n_k-m_k$ converges to $0$, $n_k$ also converges to $x_0$.
But this is where I'm stuck. I believe that $f(x_0) = g(x_0)$ but I'm unable to prove this.
Best Answer
This is the bisection method.
First consider the subsequences $(m_{k'})$ and $(n_{k'})$ such that $f(m_{k'})>g(m_{k'})$ and $f(n_{k'})<g(n_{k'})$.
If there is no such subsequence, then consider the subsequence $(m_{k''})$ and $(n_{k''})$ such that $f(m_{k''})<g(m_{k''})$ and $f(n_{k''})>g(n_{k''})$.
Passing to the limit in any of these subsequences yields (using continuity of $f,g$) that $f(x_0)\ge g(x_0)$ and $f(x_0)\le g(x_0)$. Hence $f(x_0)=g(x_0)$.