Prove that continuous functions f and g intersect 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.
 A: 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)$.
A: Suppose $f-g$ is positive at $x_0$ then it is positive in an interval containing $x_0$ and that interval contains one of the intervals $[m_r,n_r]$ in which the functions are supposed to cross - since these contain $x_0$ and become arbitrarily  narrow. Ditto for negative. This uses continuity, which you have avoided using so far and which is essential to the truth of the proposition you are trying to prove.
A: If we start with $f(a)\ge g(a)$ and $f(b)\le g(b)$, then for all $k$ we have $f(m_k)\ge g(m_k)$ and $f(n_k)\le g(n_k)$. This is because in your process of selecting intervals, we always have either $m_{k+1} = m_k$ or $n_{k+1} = n_k$. So, if at step $k$ we have (wlog) $n_{k+1} = n_k$, then $m_{k+1}$ has to satisfy the same inequality with $f$ and $g$ as $m_k$ did in order for your interval to be a crossing.
So since you have $f(m_k)\ge g(m_k)$ and $f(n_k)\le g(n_k)$ for all $k$, passing to the limit yields $f(x_0)\ge g(x_0)$ and $f(x_0)\le g(x_0)$.
A: I am elaborating on my comment using a different approach as asked by the proposer.

Bolzano's theorem: Let $f$ be a continuous function on an interval $[a,b]$ such that (without loss of generality) holds: $g(a)<0, \; g(b)>0$. Then there exists an $x_0 \in (a, b) \mid f(x_0)=0$. If $g(a)\leq 0$ and $g(b)\geq 0$ then there exists an $x_0 \in [a,b] \mid f(x_0)=0$.

We are applying the above to the function $h(x)=f(x)-g(x), \; x \in [a, b]$. Then $h$ is a continuous function since it comes from substraction of two continuous functions. However $f(a)\geq g(a)$ and $f(b) \leq g(b)$. Hence:
$$h(a)h(b)=\underbrace{f(a)-g(a)}_{\geq 0}\cdot \underbrace{f(b)-g(b)}_{\leq 0}\leq 0$$
Hence there exists an $x_0 \in [a, b]$ such that $h(x_0)=0 \Leftrightarrow f(x_0)=g(x_0)$ which is the wanted result.
