# Maximizing a Function over Integers (Part 5)

In parts 1,2, and 3, I described some theorems about finding the integer $i$ which maximizes $f(i)$, the value of a concave function $f:[a,b]\rightarrow \mathbb R$.  In part 4, I described a theorem for finding integers $i$ which maximize $f(i)$ where $f:[a,b]\rightarrow \mathbb R$ is a continuous function.  In part 5, I will describe some rather obvious, but useful facts and lemmas for finding integers $i$ which maximize $f(i)$ for any function $f:[a,b]\rightarrow \mathbb R$.

### NOTATION

•  $[a,b]$ is the set of real numbers $x$ where $a\leq x \leq b$, and $a$ and $b$ are real numbers.
• $f:[a,b]\rightarrow \mathbb R$ means that the function $f$ takes as input real numbers from $[a,b]$ and gives as outputs real numbers.  More generally, the notation  $f:A\rightarrow B$ denotes a function $f$ where the input elements are from set $A$ and the outputs are in set $B$.  For example, we could define $f:[1, 10]\rightarrow \mathbb R$ by $f(x) =\log(x)$ for real numbers $x$ between 1 and 10 where the outputs are real numbers.
• We will use  floor$(x)$  to denote the largest integer less than or equal to $x$. You can think of floor($x$) as rounding $x$ down.
• We will use  ceil$(x)$  to denote the smallest integer greater than or equal to $x$.  You can think of ceil($x$) as rounding $x$ up.

MAIN ASSUMPTION

For the rest of this post assume that $a$ and $b$ are real numbers, $a+1\leq b$, and $f$ is a real valued function with domain [a,b].  $f:[a,b] \rightarrow\mathbb{R}$, .

### DEFINITIONS

• We say that a function $f$ is increasing on the set of numbers $D$ if for all $x_1$ and $x_2$ in $D$ $$a\leq x_1 < x_2 \leq b\quad\mathrm{implies}\quad f(x_1) \leq f(x_2).$$ As the value of $x$ increases, the function increases.  If the function is differentiable, this is equivalent to the derivative being non-negative.
• We say that a function $f$ is strictly increasing on the set of numbers $D$ if for all $x_1$ and $x_2$ in $D$ $$a\leq x_1 < x_2 \leq b\quad\mathrm{implies}\quad f(x_1) <f(x_2).$$If the function is differentiable, this is almost the same as the derivative being positive.
• We say that a function $f$ is decreasing on the set of numbers $D$ if for all $x_1$ and $x_2$ in $D$ $$a\leq x_1 < x_2 \leq b\quad\mathrm{implies}\quad f(x_1) \geq f(x_2).$$ As the value of $x$ increases, the function decreases.  If the function is differentiable, this is equivalent to the derivative being non-positive.
• We say that a function $f$ is strictly decreasing on the set of numbers $D$ if for all $x_1$ and $x_2$ in $D$ $$a\leq x_1 < x_2 \leq b\quad\mathrm{implies}\quad f(x_1)>f(x_2).$$ If the function is differentiable, this is almost the same as the derivative being negative.

### SOME OBVIOUS YET USEFUL FACTS

1. If $f$ is a strictly increasing function, then the integer $i$ that maximizes $f(i)$ is $\mathrm{floor}(b)$.
2. If $f$ is an increasing function, then the set of integers that maximize $f$ is non-empty and has the form $\{j,j+1, j+2, \ldots, \mathrm{floor}(b)\}$ where $j$ is an integer and $a\leq j\leq b$.
3. If $f$ is a strictly decreasing function, then the integer $i$ that maximizes $f(i)$ is $\mathrm{ceil}(a)$.
4. If $f$ is a decreasing function, then the set of integers that maximize $f$ is non-empty and has the form $\{\mathrm{ceil}(a),\mathrm{ceil}(a)+1,\ldots, j\}$ where $j$ is an integer and $a\leq j\leq b$.
5. Suppose that the integer $i$ maximizes $f(i)$. Then either

5a) $i=\mathrm{ceil}(a)$ or $i=\mathrm{floor}(b)$ (i.e. $i$ is on the “border” of $[a,b]$), or

5b) $a+1\leq i \leq b-1$, $g(i-1) \geq 0$, and $g(i)\leq 0$ where $$g:[a, b-1]\rightarrow\mathbb R \quad\mathrm{and}\quad g(x) = f(x+1) – f(x).$$ This is equivalent to $f(i-1) \leq f(i)$ and $f(i) \geq f(i+1)$.

### TWO LEMMAS

Fact 5 is related to the following two lemmas. Assume that

• the function $g:[a, b-1]\rightarrow\mathbb{R}$ is defined by $g(x) = f(x+1) – f(x)$,
• $\gamma$ is a real number where $a+1\leq \gamma \leq b-1$,
• $g(x)>0$ if and only if $\gamma > x$, and
• $g(x)<0$ if and only if $x>\gamma$.

Lemma 1: If $\gamma$ is an integer, then the set of integers that maximize $f$ is $\{\gamma, \gamma+1\}$.
Lemma 2: If $\gamma$ is not an integer, then the unique integer that maximizes $f$ is $\mathrm{ceil}(\gamma).$

Proof: Let $i$ be an integer in $[a,b]$ that maximizes $f(i)$. (i.e. $f(i)\geq f(j)$ for all integers $j$ in $[a,b]$.)

If $\gamma > i$ then $g(i)>0$ which implies that $f(i+1)> f(i)$ in which case $f(i)$ is not the maximum of $f$ over all integers in $[a,b]$ contradicting the definition of $i$. Hence $\gamma\leq i$.

If $i-1>\gamma$ then $g(i-1)<0$ which implies that $f(i)< f(i-1)$ and again $f(i)$ is not the maximum of $f$ over all integers in $[a,b]$ contradicting the definition of $i$. Hence $i \leq \gamma+1$.

We conclude that $\gamma\leq i \leq \gamma +1$.

If $\gamma$ is not an integer, then $i=\mathrm{ceil}(\gamma)$ proving Lemma 2.

Notice that $g(\gamma)=0$, so $f(\gamma) = f(\gamma+1)$.  If $\gamma$ is an integer, then $i$ can be either $\gamma$ or $\gamma+1$ proving Lemma 1.