Maximizing a Function over Integers (Part 4)

About two years ago, I wrote 3 posts about finding the maximum of a real valued concave functions over a set of consecutive integers.

There is a related theorem for continuous functions.

Theorem:  Suppose that $f:[a,b] \rightarrow\mathbb R$ is continuous with $a+1\leq b$. Let
$$m=\max_{i\in \mathbb Z\cap[a,b]} f(i)\quad\mathrm{and}\quad S=\{ i\in \mathbb Z\cap[a,b]\, | f(i)= m\}.$$
Then $S$ is non-empty, and for all $i\in S\cap[a+1, b-1]$, there exists an $x(i)$ such that $$f(x(i)) = f(x(i)+1)$$ and $x(i)\leq i \leq x(i)+1.$

This is very nice if it is easy to find all the solutions to $f(x) = f(x+1)$ where $a\leq x \leq b$.  If you find those solutions, then the maximizer of $f$ over the set of integers in $[a,b]$ is either the smallest integer in $[a, b]$, the largest integer in $[a, b]$, or it is in the set $[x,x+1]$ where $x$ is one of the solutions to $f(x)=f(x+1)$.

More formally, if $i$ is an integer in $[a,b]$ and $f(i)\geq f(j)$ for all integers $j\in[a,b]$, then either

  1. $i$ is on the “border” of $[a, b]$, i.e. $i\in [a, a+1)\cup (b-1, b]$, or
  2. there exists a real number $x\in[a, b-1]$ such that $x\leq i \leq x+1$ and $f(x) = f(x+1).$


Proof of the Theorem:

$S$ is non-empty because $[a,b]\cap\mathbb Z$ is compact. Now for any $i\in S\cap[a+1, b-1]$, one of the three following cases must hold,

Case 1: $f(i-1) = f(i)$. In this case, let $x(i) = i-1$ and the theorem holds.

Case 2: $f(i) = f(i+1)$ In this case, let $x(i) = i$ and the theorem holds.

Case 3: $f(i-1) < f(i)$ and $f(i+1) < f(i)$. For this case, define $g:[a, b-1]\rightarrow \mathbb R$ by $$g(x) = f(x+1) – f(x).$$ The continuity of $f$ implies that $g$ is continuous. Also, $g(i-1) >0$, and $g(i)<0$, so by the intermediate value theorem, there exists an $x^*\in(i-1, i)$ such that
g(x^*) &=0\quad\mathrm{thus}\\
f(x^* +1) – f(x^*) &=0.
Setting $x(i)=x^*$ satisfies the theorem for case 3.

We have shown that in all three cases, there exists an $x(i)$ such that $x(i)\leq i \leq x(i)+1$ and $f(x(i)) = f(x(i)+1)$ proving the theorem.