The following function has come up twice in my research

$$f(a,b)=\frac{\ln(b)-\ln(a)}{b-a}$$ where $0<a<b.$

Now, I had known that if $a$ and $b$ are close, then $$f(a,b)\approx\frac{1}{\mathrm{mean}(a,b)}$$ and $$\frac{1}{b}<f(a,b)<\frac1{a}.$$ But last week, with a little help from GPT, I got some better approximations and bounds on $f(a,b)$.

Let $m=(a+b)/2$ and $\Delta = (b-a)/2$.

Below GPT and I derive the following

• $$1/b < f(a,b) < 1/a,$$
• $$1/m <  f(a,b) < 1/m + \frac{\Delta^2}{3m}\left(\frac{1}{m^2-\Delta^2 }\right),$$
• $$ -\frac{2\Delta^4}{15a^5}< f(a,b)\; – \frac{1}{6}\left(\frac{1}{a}+\frac{4}{m}+\frac{1}{b}\right) < -\frac{2\Delta^4}{15b^5},\mathrm{\ and}$$
• $$\begin{aligned} f(a,b) &= \frac{ \tanh^{-1}(\Delta/m)}{\Delta} = \frac1{m} \frac{ \tanh^{-1}(\Delta/m)}{\Delta/m}\\&= \frac{1}{\Delta} \left(\frac{\Delta}{m} + \frac{\Delta^3}{3m^3}+ \frac{\Delta^5}{5m^5} + \cdots\right)\\  &= \frac{1}{m} \left(1 + \frac{\Delta^2}{3m^2}+ \frac{\Delta^4}{5m^4} + \cdots\right) \end{aligned}$$

where  $$ \tanh^{-1}(y) = x$$ if and only if $$\tanh(x) := \frac{ e^x-e^{-x}}{e^x + e^{-x}} =y$$ for any $x\in\mathbb{R}$ and $y\in(-1,1)$.

(Alternatively, $$\tanh^{-1}(x) = \frac{1}{2} \ln (x+1)-\frac{1}{2} \ln (1-x)$$ where $\ln(x)$ is the natural log and $|x|<1$.)

The derivation

At first I tried to use Taylor Series to bound $f(a,b)$, but it was a bit convoluted so I asked GPT. GPT created a much nicer, simpler proof. (See this PDF). GPT’s key observation was that $$f(a,b)= \frac{\ln(b)-\ln(a)}{b-a} = \frac{1}{b-a}\int_a^b \frac{dx}{x}$$ is the mean value of $1/x$ over the interval $[a,b]$. (In truth, I felt a bit dumb for not having noticed this. Lol.)

GPT’s observation inspires a bit more analysis.

Let $$z= \frac{x}{m} -1,\mathrm{\ so\ \ } m(z+1)=x.$$ If $x=a$, then
$$z= \frac{a}{m} -1= \frac{m-\Delta}{m} – 1= -\frac{\Delta}{m}.$$
Similarly, if $x=b$,
$$z= \frac{b}{m} -1= \frac{m+\Delta}{m} – 1= \frac{\Delta}{m}.$$
Applying these substitutions to the integral yields
$$\begin{aligned}
\int_{x=a}^{x=b} \frac{dx}{x} &=\int_{z=-\Delta/m}^{z=\Delta/m}\frac{m\;dz}{m(z+1)} \\
&=\int_{z=-\Delta/m}^{z=\Delta/m}\frac{dz}{z+1} \\
&=\int_{z=-\Delta/m}^{z=\Delta/m} (1-z+z^2-z^3+\cdots)dz\\
&=\int_{z=-\Delta/m}^{z=\Delta/m} (1+z^2+z^4+\cdots)dz\\
&=\int_{z=-\Delta/m}^{z=\Delta/m} \frac{dz}{1-z^2}\\
&=\left.\tanh^{-1}(z)\right|_{z=-\Delta/m}^{z=\Delta/m} \\
&= \tanh^{-1}(\Delta/m) – \tanh^{-1}(-\Delta/m)\\
&= 2 \tanh^{-1}(\Delta/m).
\end{aligned}$$
(Above we twice applied the wonderful thumb rule $$\frac{1}{1-x} = 1+ x + x^2 +x^3+\dots$$ if $|x|<1$. See idea #87 from the top 100 math ideas.)

So,
$$\frac{\ln(b) – \ln(a)}{b-a} =\frac{ 2 \tanh^{-1}(\Delta/m)}{b-a}=\frac{ \tanh^{-1}(\Delta/m)}{\Delta}.$$

Furthermore,
$$
\tanh^{-1}(x) = x + x^3/3 + x^5/5 + \cdots,
$$
so
$$\begin{aligned}
f(a,b) = \frac{\ln(b) – \ln(a)}{b-a} &= \frac{1}{\Delta} \left(\frac{\Delta}{m} + \frac{\Delta^3}{3m^3}+ \frac{\Delta^5}{5m^5} + \cdots\right) \\
&=\frac{1}{m} + \frac{\Delta^2}{3m^3}+ \frac{\Delta^4}{5m^5} + \frac{\Delta^6}{7m^7} + \cdots
\end{aligned}$$
This series gives us some nice approximations of $f(a,b)$ when $\Delta/m<1/2$. We can also bound the error of the approximation $$f(a,b)\approx 1/m$$ as follows $$\begin{aligned}
\frac{1}{m} <\frac{\ln(b) – \ln(a)}{b-a}&=\frac{1}{m} + \frac{\Delta^2}{3m^3}+ \frac{\Delta^4}{5m^5} + \frac{\Delta^6}{7m^7} + \cdots \\
&<\frac{1}{m} + \frac{\Delta^2}{3m^3}+ \frac{\Delta^4}{3m^5} + \frac{\Delta^6}{3m^7} + \cdots \\
&=\frac{1}{m} + \frac{\Delta^2}{3m^3}(1 + \frac{\Delta^2}{m^2} + \frac{\Delta^4}{m^4} + \cdots )\\
&=\frac{1}{m} + \frac{\Delta^2}{3m^3}\left(\frac{1}{1-\frac{\Delta^2}{m^2} }\right)\\
&=\frac{1}{m} + \frac{\Delta^2}{3m}\left(\frac{1}{m^2-\Delta^2 }\right).\\
\end{aligned} $$

Example.

Let $a= 6/100$ and $b=7/100$. Then $m=13/200$, $\Delta = 1/200$,

• $$\frac{\ln(b)-\ln(a)}{b-a}= \tanh^{-1}(\Delta/m)/\Delta \approx 15.415067982725830429,$$
• $$1/m \approx 15.3846,$$
• $$1/m + \Delta^2/(3 m^3)\approx 15.41496,\ \mathrm{and}$$
• $$1/m + \Delta^2/(3 m^3) + \Delta^4/(5 m^5)\approx 15.4150675.$$
• $$1/m+ \frac{\Delta^2}{3m}\left(\frac{1}{m^2-\Delta^2 }\right)\approx 15.41514$$

Applying Simpson’s Rule

We can also use Simpson’s rule to approximate $\ln(b)-\ln(a)$.  The error formula for Simpson’s rule is

$$\begin{align}\int_{a}^{b}g(x)\,dx&=\frac{\Delta}{3}[g(a)+4g(m)+g(b)]-\frac{\Delta^5}{90}g^{(4)}(\xi)\end{align}$$

for some $\xi$ in the interval $(a,b)$. Setting $g(x)=1/x$, $$I=\ln(b)-\ln(a),\quad\mathrm{ and }\quad h(a,b)= \frac{\Delta}{3}\left(\frac{1}{a}+\frac{4}{m}+\frac{1}{b}\right)$$ with $m=(a+b)/2$ and $\Delta=(b-a)/2$ gives

$$\begin{align} \ln(b) – \ln(a) &=\frac{\Delta}{3}\left(\frac{1}{a}+\frac{4}{m}+\frac{1}{b}\right)-\frac{\Delta^5}{90}\frac{24}{\xi^5} \\ I&=h(a,b)-\frac{4\Delta^5}{15\xi^5}\\I-h(a,b) &= -\frac{4\Delta^5}{15\xi^5}\\-\frac{4\Delta^5}{15a^5}&< I-h(a,b) < -\frac{4\Delta^5}{15b^5}.\end{align}$$

Now we divide by $2\Delta = b-a$ to conclude that
$$\begin{aligned}\frac{\ln(b) – \ln(a)}{b-a}&= \frac{1}{6}\left(\frac{1}{a}+\frac{8}{a+b}+\frac{1}{b}\right) + error \\&= \frac{1}{6}\left(\frac{1}{a}+\frac{4}{m}+\frac{1}{b}\right) + error \\&\approx \frac{1}{6}\left(\frac{1}{a}+\frac{4}{m}+\frac{1}{b}\right) -\frac{2\Delta^4}{15m^5}\end{aligned}$$
where
$$ -\frac{2\Delta^4}{15a^5}< error < -\frac{2\Delta^4}{15b^5}.$$

(Thanks to GPT and StackEdit(https://stackedit.io/).)

In the previous 5 parts, I described several theorems which are useful for finding the maximum value of a function $f$ over integers.  In parts 1, 2, and 3, $f$ was concave.  In part 4, $f$ was continuous.  And in part 5, there were no restrictions on $f$.  In this post, the focus is on finding the maximum value of an investment game function over integers.

What is the maximum of $$f(x)=\exp(\alpha x) (T-x)$$ over all integers?  This function appears in several investment board games including Terraforming Mars, Master of Orion, and Roll for the Galaxy.

EXAMPLE $f(x)=\exp(\alpha x) (T-x)$

Let’s find the maximum of $f:\mathbb{R}\rightarrow\mathbb R$ where $$f(x)=\exp(\alpha x) (T-x),$$ $\alpha>0$, and $T>0$. The $\exp(\alpha x)$ is always postive, so $$f(x)>0\quad\mathrm{\ if\ and\ only\ if\ } x<T.$$

Let $g(x) = f(x+1) – f(x)$ as in “Maximizing a Function over Integers (Part 5)“. Let $\beta=\exp(\alpha)$. We can use some algebra to better understand the behavior of $g$.

$$\begin{aligned}g(x) &= f(x+1) – f(x)\\&= \exp(\alpha (x+1)) (T-(x+1)) – \exp(\alpha x) (T-x)\\&= \beta\beta^x (T-x -1) – \beta^x (T-x)\\&= \beta^x [ \beta(T-x -1) - T+x]\\&=\beta^x [ (1-\beta) x + (\beta-1) T -\beta]\\&=\beta^x [ (\beta-1)(T-x) -\beta].\end{aligned}
$$

So $g(x)>0$ if and only if

$$\begin{aligned}(\beta-1)(T-x) -\beta &>0\\(\beta-1)(T-x) &>\beta\\T-x &>\frac{\beta}{\beta-1} \\T- \frac{\beta}{\beta-1} &> x\\\gamma &> x\end{aligned}
$$
where $$\gamma=T- \frac{\beta}{\beta-1}.$$ Consequently,

$g(x)<0$ if and only if $\gamma < x$,

and by reversing the inequalities in the argument above,

$g(x)>0$ if and only if $\gamma > x$.

(This statement implies that if we restrict $f$ to integer inputs, then $f$ is increasing for inputs less than $\gamma-1$ and decreasing for inputs greater than $\gamma$.)

We can apply the lemmas from Part 5 to conclude that

– if $\gamma$ is an integer, then the maximum value of $f$ amoung all integers is $f(\gamma)$ which is also equal to $f(\gamma+1)$, and
– if $\gamma$ is not an integer, then the maximum value of $f$ amoung all integers is $f(\mathrm{ceil}(\gamma))$ and that maximum value is only attained by the input $\mathrm{ceil}(\gamma)$.

(Technical note: The lemmas in Part 5 can be applied with $b=T+1$ and and real number $a<\gamma-1$.)

$f(x) = 1.1^x (100-x)$

For example, if $$f(x) = 1.1^x (100-x)=\exp(\alpha x)(T-x)$$ with $\alpha=\log(1.1)$ and $T=100$, then

$$\begin{aligned}\beta=\exp(\alpha)&=\exp(\log(1.1)) = 1.1,\quad\mathrm{and}\\ \gamma= T- \frac{\beta}{\beta-1}&= 100- \frac{1.1}{1.1-1}= 100 -11 = 89.\end{aligned}$$

We conclude that the maximum value of $f$ over all integers is $$f(\gamma) =f(\gamma+1) = f(89)=f(90)\approx53130.2$$ Note that $f(88) \approx 52691.1$ and $f(91)\approx 52598.9$.

$f(x)=(1+1/k)^x(T-x).$ for any positive integer $k$

More generally, let $k$ be any positive integer and let $$f(x)=(1+1/k)^x(T-x).$$
Then $$f(x)=\exp(\alpha x)(T-x)$$ with $\alpha=\log(1+1/k),$

$$\begin{aligned}\beta=\exp(\alpha)&=\exp(\log(1+1/k)) =1+1/k,\quad\mathrm{and}\\\gamma= T- \frac{\beta}{\beta-1}&= T – \frac{1+1/k}{1+1/k-1}= T- (k+1) .\end{aligned}$$

We conclude that the maximum value of $f$ over all integers is $$f(\gamma) =f(\gamma+1) = f(T-k-1)=f(T-k).$$

AcknowledgmentS

Thanks to stackedit.io for helping me write the TeX.  GPT3 also recommended a change to one of the sentences in the introductory paragraph.

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.