Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-05T05:46:18.334Z Has data issue: false hasContentIssue false

Maximizing weighted sums of binomial coefficients using generalized continued fractions

Published online by Cambridge University Press:  27 August 2024

S.P. Glasby*
Affiliation:
Center for the Mathematics of Symmetry and Computation, University of Western Australia, Perth 6009, Australia ([email protected])
G.R. Paseman
Affiliation:
Sheperd Systems, UC Berkeley, USA ([email protected])
*
*Corresponding author.
Rights & Permissions [Opens in a new window]

Abstract

Let $m,\,r\in {\mathbb {Z}}$ and $\omega \in {\mathbb {R}}$ satisfy $0\leqslant r\leqslant m$ and $\omega \geqslant 1$. Our main result is a generalized continued fraction for an expression involving the partial binomial sum $s_m(r) = \sum _{i=0}^r\binom{m}{i}$. We apply this to create new upper and lower bounds for $s_m(r)$ and thus for $g_{\omega,m}(r)=\omega ^{-r}s_m(r)$. We also bound an integer $r_0 \in \{0,\,1,\,\ldots,\,m\}$ such that $g_{\omega,m}(0)<\cdots < g_{\omega,m}(r_0-1)\leqslant g_{\omega,m}(r_0)$ and $g_{\omega,m}(r_0)>\cdots >g_{\omega,m}(m)$. For real $\omega \geqslant \sqrt 3$ we prove that $r_0\in \{\lfloor \frac {m+2}{\omega +1}\rfloor,\,\lfloor \frac {m+2}{\omega +1}\rfloor +1\}$, and also $r_0 =\lfloor \frac {m+2}{\omega +1}\rfloor$ for $\omega \in \{3,\,4,\,\ldots \}$ or $\omega =2$ and $3\nmid m$.

Type
Research Article
Copyright
Copyright © The Author(s), 2024. Published by Cambridge University Press on behalf of The Royal Society of Edinburgh

1. Introduction

Given a real number $\omega \geqslant 1$ and integers $m,\,r$ satisfying $0\leqslant r\leqslant m$, set

(1.1)\begin{equation} s_m(r):=\sum_{i=0}^r\binom{m}{i}\quad\text{and}\quad g(r)= g_{\omega,m}(r):=\omega^{{-}r}s_m(r), \end{equation}

where the binomial coefficient $\binom{m}{i}$ equals $\prod _{k=1}^i\frac {m-k+1}{k}$ for $i>0$ and $\binom{m}{0}=1$. The weighted binomial sum $g_{\omega,m}(r)$ and the partial binomial sum $s_m(r)=g_{1,m}(r)$ appear in many formulas and inequalities, e.g. the cumulative distribution function $2^{-m}s_m(r)$ of a binomial random variable with $p=q=\tfrac {1}{2}$ as in remark 5.3, and the Gilbert–Varshamov bound [Reference Ling and Xing6, Theorem 5.2.6] for a code $C\subseteq \{0,\,1\}^n$. Partial sums of binomial coefficients are found in probability theory, coding theory, group theory, and elsewhere. As $s_m(r)$ cannot be computed exactly for most values of $r$, it is desirable for certain applications to find simple sharp upper and lower bounds for $s_m(r)$. Our interest in bounding $2^{-r}s_m(r)$ was piqued in [Reference Glasby and Paseman4] by an application to Reed–Muller codes $\textrm{RM}(m,\,r)$, which are linear codes of dimension $s_m(r)$.

Our main result is a generalized continued fraction $a_0 + \mathcal{K}_{i=1}^{r} \frac {b_i}{a_i}$ (using Gauss’ Kettenbruch notation) for $Q:=\frac {(r+1)}{s_m(r)}\binom{m}{r+1}$. From this we derive useful approximations to $Q,\, 2+\frac {Q}{r+1}$, and $s_m(r)$, and with these find a maximizing input $r_0$ for $g_{\omega,m}(r)$.

The $j$th tail of the generalized continued fraction $\mathcal{K}_{i=1}^{r} \frac {b_i}{a_i}$ is denoted by ${\mathcal {T}}_j$ where

(1.2)\begin{equation} {\mathcal{T}}_j:=\mathop{{\vcenter{\hbox{ $\mathcal{K}$}}}}_{i=j}^{r} \frac{b_i}{a_i}= \frac{b_j}{a_j +\dfrac{b_{j+1}}{a_{j+1} +\dfrac{b_{j+2}}{\llap{{\ddots}} {{a_{r-1} + \dfrac{b_r}{a_r}}}}}} =\frac{b_j}{a_j+{\mathcal{T}}_{j+1}} \quad\textrm{and}\ 1\leqslant j\leqslant r. \end{equation}

If ${\mathcal {T}}_j=\frac {B_j}{A_j}$, then ${\mathcal {T}}_j=\frac {b_j}{a_j+{\mathcal {T}}_{j+1}}$ shows $b_jA_j-a_jB_j={\mathcal {T}}_{j+1}B_j$. By convention we set ${\mathcal {T}}_{r+1}=0$.

It follows from $\binom{m}{r-i}=\binom{m}{r}\prod _{k=1}^i\frac {r-k+1}{m-r+k}$ that $x^i\binom{m}{r}\leqslant \binom{m}{r-i}\le y^i\binom{m}{r}$ for $0\leqslant i\leqslant r$ where $x:=\frac {1}{m}$ and $y:=\frac {r}{m-r+1}$. Hence $\frac {1-x^{r+1}}{1-x}\binom{m}{r}\leqslant s_m(r)\leqslant \frac {1-y^{r+1}}{1-y}\binom{m}{r}$. These bounds are close if $\frac {r}{m}$ is near 0. If $\frac {r}{m}$ is near $\tfrac {1}{2}$ then better approximations involve the Berry–Esseen inequality [Reference Nagaev and Chebotarev7] to estimate the binomial cumulative distribution function $2^{-m}s_m(r)$. The cumulative distribution function $\Phi (x)=\frac {1}{\sqrt {2\pi }}\int _{-\infty }^xe^{-t^2/2}\,dt$ is used in remark 5.3 to show that $|2^{-m}s_m(r)-\Phi (\frac {2r-m}{\sqrt {m}})|\leqslant \frac {0.4215}{\sqrt {m}}$ for $0\leqslant r\leqslant m$ and $m\ne 0$. Each binomial $\binom{m}{i}$ can be estimated using Stirling's approximation as in [Reference Stănică10, p. 2]: $\binom{m}{i}=\frac {C_i^m}{\sqrt {2\pi p(1-p)m}}\left (1+O\left (\frac {1}{m}\right )\right )$ where $C_i=\frac {1}{p^p(1-p)^{1-p}}$ and $p=p_i=i/m$. However, the sum $\sum _{i=0}^r\binom{m}{i}$ of binomials is harder to approximate. The preprint [Reference Worsch11] discusses different approximations to $s_m(r)$.

Sums of binomial coefficients modulo prime powers, where $i$ lies in a congruence class, can be studied using number theory, see [Reference Granville5, p. 257]. Theorem 1.1 below shows how to find excellent rational approximations to $s_m(r)$ via generalized continued fractions.

Theorem 1.1 Fix $r,\,m\in {\mathbb {Z}}$ where $0\leqslant r\leqslant m$ and recall that $s_m(r)=\sum _{i=0}^r\binom{m}{i}$.

  1. (a) If $b_i=2i(r+1-i)$, $a_i=m-2r+3i$ for $0\leqslant i\leqslant r$, then

    \[ Q:=\frac{(r+1)\binom{m}{r+1}}{s_m(r)}=a_0+{\vcenter{\hbox{ $\mathcal{K}$}}}_{i=1}^{r} \frac{b_i}{a_i}. \]
  2. (b) If $1\leqslant j\leqslant r$, then ${\mathcal {T}}_j=R_j/R_{j-1}>0$ where the sum $R_j:= 2^j j!\sum _{k=0}^{r-j}\binom{r-k}{j}\binom{m}{k}$ satisfies $b_j R_{j-1} - a_j R_j = R_{j+1}$. Also, $(m-r)\binom{m}{r}-a_0R_0=R_1$.

Since $s_m(m)=2^m$, it follows that $s_m(m-r)=2^m-s_m(r-1)$ so we focus on values of $r$ satisfying $0\leqslant r\leqslant \lfloor \frac {m}{2}\rfloor$. Theorem 1.1 allows us to find a sequence of successively sharper upper and lower bounds for $Q$ (which can be made arbitrarily tight), the coarsest being $m-2r\leqslant Q\leqslant m-2r+\frac {2r}{m-2r+3}$ for $1\leqslant r<\frac {m+3}{2}$, see proposition 2.3 and corollary 2.4.

The fact that the tails ${\mathcal {T}}_1,\,\ldots,\,{\mathcal {T}}_r$ are all positive is unexpected as $b_i/a_i$ is negative if $\frac {m+3i}{2}< r$. This fact is crucial for approximating ${\mathcal {T}}_1=\mathcal{K}_{i=1}^{r} \frac {b_i}{a_i}$, see theorem 1.3. Theorem 1.1 implies that ${\mathcal {T}}_1{\mathcal {T}}_2\cdots {\mathcal {T}}_r=R_r/R_0$. Since $R_0=s_m(r)$, $R_r=2^rr!$, ${\mathcal {T}}_j=\frac {b_j}{a_j+{\mathcal {T}}_{j+1}}$ and $\prod _{j=1}^rb_j=2^r(r!)^2$, the surprising factorizations below follow c.f. remark 2.1.

Corollary 1.2 We have $s_m(r)\prod _{j=1}^r{\mathcal {T}}_j=2^rr!$ and $r!s_m(r)=\prod _{j=1}^r(a_j+{\mathcal {T}}_{j+1})$.

Suppose that $\omega >1$ and write $g(r)=g_{\omega,m}(r)$. We extend the domain of $g(r)$ by setting $g(-1)=0$ and $g(m+1)=\frac {g(m)}{\omega }$ in keeping with (1.1). It is easy to prove that $g(r)$ is a unimodal function c.f. [Reference Byun and Poznanović2, § 2]. Hence there exists some $r_0\in \{0,\,1,\,\ldots,\,m\}$ that satisfies

(1.3)\begin{align} & g_{\omega,m}({-}1)<\cdots< g_{\omega,m}(r_0-1)\leqslant g_{\omega,m}(r_0)\quad\text{and}\qquad\notag\\& g_{\omega,m}(r_0)>\cdots>g_{\omega,m}(m+1). \end{align}

As $g(-1)< g(0)=1$ and $\left (\frac {2}{\omega }\right )^m=g(m)>g(m+1)=\frac {2^m}{\omega ^{m+1}}$, both chains of inequalities are non-empty. The chains of inequalities (1.3) serve to define $r_0$.

We use theorem 1.1 to show that $r_0$ is commonly close to $r':=\lfloor \frac {m+2}{\omega +1}\rfloor$. We always have $r'\leqslant r_0$ (by lemma 3.3) and though $r_0-r'$ approaches $\frac {m}{2}$ as $\omega$ approaches 1 (see remark 4.4), if $\omega \geqslant \sqrt {3}$ then $0\leqslant r_0 - r'\leqslant 1$ by the next theorem.

Theorem 1.3 If $\omega \geqslant \sqrt {3}$, $m\in \{0,\,1,\,\ldots \}$ and $r':=\lfloor \frac {m+2}{\omega +1}\rfloor$, then $r_0\in \{r',\,r'+1\}$, that is

\[ g(0)<\cdots< g(r'-1)\leqslant g(r'),\quad\text{and}\quad g(r'+1)>g(r'+2)>\cdots>g(m). \]

Sharp bounds for $Q$ seem powerful: they enable short and elementary proofs of results that previously required substantial effort. For example, our proof in [Reference Glasby and Paseman4, Theorem 1.1] for $\omega =2$ of the formula $r_0=\lfloor \frac {m}{3}\rfloor +1$ involved a lengthy argument, and our first proof of theorem 1.4 below involved a delicate induction. By this theorem there is a unique maximum, namely $r_0=r'=\lfloor \frac {m+2}{\omega +1}\rfloor$ when $\omega \in \{3,\,4,\,5,\,\ldots \}$ and $\omega \ne m+1$, c.f. remark 4.2. In particular, strict inequality $g_{\omega,m}(r'-1)< g_{\omega,m}(r')$ holds.

Theorem 1.4 Suppose that $\omega \in \{3,\,4,\,5,\,\ldots \}$ and $r'=\lfloor \frac {m+2}{\omega +1}\rfloor$. Then

\[ g_{\omega,m}(0)<\cdots< g_{\omega,m}(r'-1)\leqslant g_{\omega,m}(r')>g_{\omega,m}(r'+1)>\cdots>g_{\omega,m}(m), \]

with equality if and only if $\omega =m+1$.

Our motivation was to analyse $g_{\omega,m}(r)$ by using estimates for $Q$ given by the generalized continued fraction in theorem 1.1. This gives tighter estimates than the method involving partial sums used in [Reference Glasby and Paseman4]. The plots of $y=g_{\omega,m}(r)$ for $0\leqslant r\leqslant m$ are highly asymmetrical if $\omega -1$ and $m$ are small. However, if $m$ is large the plots exhibit an ‘approximate symmetry’ about the vertical line $r=r_0$ (see figure 1). Our observation that $r_0$ is close to $r'$ for many choices of $\omega$ was the starting point of our research.

Figure 1. Plots of $y=g_{\omega,24}(r)$ for $0\leqslant r\leqslant 24$ with $\omega \in \{1,\,\frac 32,\,2,\,3\}$, and $y=g_{3,12}(r)$

Byun and Poznanović [Reference Byun and Poznanović2, Theorem 1.1] compute the maximizing input, call it $r^*$, for the function $f_{m,a}(r):=(1+a)^{-r}\sum _{i=0}^r\binom{m}{i}a^i$ where $a\in \{1,\,2,\,\ldots \}$. Their function equals $g_{\omega,m}(r)$ only when $\omega =1+a=2$. Some of their results and methods are similar to those in [Reference Glasby and Paseman4] which studied the case $\omega =2$. They prove that $r^*=\lfloor \frac {a(m+1)+2}{2a+1}\rfloor$ provided $m\not \in \{3,\,2a+4,\,4a+5\}$ or $(a,\,m)\ne (1,\,12)$ when $r^*=\lfloor \frac {a(m+1)+2}{2a+1}\rfloor -1$.

In Section 2 we prove theorem 1.1 and record approximations to our generalized continued fraction expansion. When $m$ is large, the plots of $y=g_{\omega,m}(r)$ are reminiscent of a normal distribution with mean $\mu \approx \frac {m}{\omega +1}$. Section 3 proves key lemmas for estimating $r_0$, and applies theorem 1.1 to prove theorem 1.4. Non-integral values of $\omega$ are considered in Section 4 where theorem 1.3 is proved. In Section 5 we estimate the maximum height $g(r_0)$ using elementary methods and estimations, see lemma 5.1. A ‘statistical’ approximation to $s_m(r)$ is given in remark 5.3, and it is compared in remark 5.4 to the ‘generalized continued fraction approximations’ of $s_m(r)$ in proposition 2.3.

2. Generalized continued fraction formulas

In this section we prove theorem 1.1, namely that $Q:=\frac {r+1}{s_m(r)}\binom{m}{r+1}=a_0+{\mathcal {T}}_1$ where ${\mathcal {T}}_1=\mathcal{K}_{i=1}^r\frac {b_i}{a_i}$. The equality $s_m(r)=\frac {r+1}{a_0+{\mathcal {T}}_1}\binom{m}{r+1}$ is noted in corollary 2.2.

A version of theorem 1.1(a) was announced in the SCS2022 Poster room, created to run concurrently with vICM 2022, see [Reference Paseman9].

Proof Proof of theorem 1.1

Set $R_{-1}=Q\,s_m(r)=(r+1)\binom{m}{r+1}=(m-r)\binom{m}{r}$ and

\[ R_j=2^j j!\sum_{k=0}^{r-j}\binom{r-k}{j}\binom{m}{k} \quad\text{for } 0\leqslant j\leqslant r+1. \]

Clearly $R_0=s_m(r)$, $R_{r+1}=0$ and $R_j>0$ for $0\leqslant j\leqslant r$. We will prove in the following paragraph that the quantities $R_j$, $a_j=m-2r+3j$, and $b_j=2j(r+1-j)$ satisfy the following $r+1$ equations, where the first equation (2.1) is atypical:

(2.1)\begin{align} R_{{-}1}-a_0R_0& =R_1, \end{align}
(2.2)\begin{align} b_jR_{j-1}-a_jR_j& =R_{j+1}\quad\text{where } 1\leqslant j\leqslant r. \end{align}

Assuming (2.2) is true, we prove by induction that ${\mathcal {T}}_{j}=R_{j}/R_{j-1}$ holds for $r+1\geqslant j\geqslant 1$. This is clear for $j=r+1$ since ${\mathcal {T}}_{r+1}=R_{r+1}=0$. Suppose that $1\leqslant j\leqslant r$ and ${\mathcal {T}}_{j+1}=R_{j+1}/R_{j}$ holds. We show that ${\mathcal {T}}_{j}=R_{j}/R_{j-1}$ holds. Using (2.2) and $R_j>0$ we have $b_jR_{j-1}/R_j-a_j=R_{j+1}/R_j={\mathcal {T}}_{j+1}$. Hence $R_j/R_{j-1}=b_j/(a_j+{\mathcal {T}}_{j+1})={\mathcal {T}}_j$, completing the induction. Equation (2.1) gives $Q=R_{-1}/R_0=a_0+R_1/R_{0}=a_0+{\mathcal {T}}_1$ as claimed. Since $R_j>0$ for $0\leqslant j\leqslant r$, we have ${\mathcal {T}}_{j}=R_{j}/R_{j-1}>0$ for $1\leqslant j\leqslant r$. This proves the first half of theorem 1.1(b), and the recurrence ${\mathcal {T}}_j=b_j/(a_j+{\mathcal {T}}_{j+1})$ for $1\leqslant j\leqslant r$, proves part (a).

We now show that (2.1) holds. The identity $R_0=2^00!\sum _{k=0}^r\binom{m}{k}=s_m(r)$ gives

\begin{align*} R_{{-}1}-a_0R_0& =(r+1)\binom{m}{r+1}-(m-2r)\sum_{i=0}^r\binom{m}{i}\\ & =(r+1)\binom{m}{r+1}-\sum_{i=0}^r({-}i+m-i-2r+2i)\binom{m}{i}\\ & =\sum_{i=0}^{r} \left[(i+1)\binom{m}{i+1}-(m-i)\binom{m}{i}\right] +2\sum_{i=0}^{r-1}(r-i)\binom{m}{i}. \end{align*}

As $(i+1)\binom{m}{i+1}=(m-i)\binom{m}{i}$, we get $R_{-1}-a_0R_0=2\sum _{k=0}^{r-1}\binom{r-k}{1}\binom{m}{k}=R_1$.

We next show that (2.2) holds. In order to simplify our calculations, we divide by $C_{j}:= 2^j j!$. Using $(j+1)\binom{r-k}{j+1}=(r-k-j)\binom{r-k}{j}$ gives

\begin{align*} \frac{R_{j+1}}{C_j} & =\sum_{k=0}^{r-j-1}2(j+1)\binom{r-k}{j+1}\binom{m}{k}\\ & =\sum_{k=0}^{r-j}2(r-k-j)\binom{r-k}{j}\binom{m}{k}\\ & =\sum_{k=0}^{r-j+1}(j-k)\binom{r-k}{j}\binom{m}{k} - \sum_{k=0}^{r-j}(k-2r+3j)\binom{r-k}{j}\binom{m}{k} \end{align*}

noting that the term with $k=r-j+1$ in the first sum is zero as $\binom{j-1}{j}=0$. Using the abbreviation $L=\sum _{k=0}^{r-j}(k-2r+3j)\binom{r-k}{j}\binom{m}{k}$ and using the identity $j\binom{r-k}{j}=(r+1-j-k)\binom{r-k}{j-1}$ gives

\begin{align*} \frac{R_{j+1}}{C_j}& =\sum_{k=0}^{r-j+1} \left[(r+1-j-k)\binom{r-k}{j-1}-k\binom{r-k}{j}\right] \binom{m}{k} -L\\ & = \sum_{k=0}^{r-j+1} \left[(r+1-j)\binom{r-k}{j-1}-k\binom{r-k}{j-1} -k\binom{r-k}{j}\right]\binom{m}{k} -L\\ & = \sum_{k=0}^{r-j+1} \left[(r+1-j)\binom{r-k}{j-1}-k\binom{r-k+1}{j}\right]\binom{m}{k} -L. \end{align*}

However, $k\binom{m}{k}=(m-k+1)\binom{m}{k-1}$, and therefore,

\begin{align*} \sum_{k=0}^{r-j+1}k\binom{r-k+1}{j}\binom{m}{k} & =\sum_{k=1}^{r-j+1}(m-k+1)\binom{r-k+1}{j}\binom{m}{k-1}\\ & =\sum_{\ell=0}^{r-j}(m-\ell)\binom{r-\ell}{j}\binom{m}{\ell}. \end{align*}

Thus

\begin{align*} \frac{R_{j+1}}{C_{j}} & =\sum_{k=0}^{r-j+1}(r-j+1)\binom{r-k}{j-1}\binom{m}{k} -\sum_{k=0}^{r-j}(m-k)\binom{r-k}{j}\binom{m}{k} -L\\ & =\sum_{k=0}^{r-j+1}(r-j+1)\binom{r-k}{j-1}\binom{m}{k} -\sum_{k=0}^{r-j}(m-k+k-2r+3j)\binom{r-k}{j}\binom{m}{k}\\ & =\sum_{k=0}^{r-j+1}(r-j+1)\binom{r-k}{j-1}\binom{m}{k} - \sum_{k=0}^{r-j}\overbrace{(m-2r+3j)}^{a_j}\binom{r-k}{j}\binom{m}{k}\\ & =\frac{\overbrace{2j(r-j+1)}^{b_j}2^{j-1}(j-1)!}{C_{j}}\sum_{k=0}^{r-j+1} \binom{r-k}{j-1}\binom{m}{k} - \sum_{k=0}^{r-j}a_j\binom{r-k}{j}\binom{m}{k} \end{align*}

Hence $\frac {R_{j+1}}{C_{j}}=\frac {b_{j}R_{j-1}}{C_{j}}-\frac {a_{j}R_{j}}{C_{j}}$ for $1\leqslant j\leqslant r$. When $j=r$, our convention gives $R_{r+1}=0$. This proves part (b) and completes the proof of part (a).

Remark 2.1 View $m$ as an indeterminant, so that $r!s_m(r)$ is a polynomial in $m$ over ${\mathbb {Z}}$ of degree $r$. The factorization $r!s_m(r)=\prod _{j=1}^r(a_j+{\mathcal {T}}_{j+1})$ in corollary 1.2 involves the rational functions $a_j+{\mathcal {T}}_{j+1}$. However, theorem 1.1(b) gives ${\mathcal {T}}_{j+1}=\frac {R_{j+1}}{R_{j}}$, so that $a_j+{\mathcal {T}}_{j+1}=\frac {a_{j}R_{j}+R_{j+1}}{R_j}=\frac {b_{j}R_{j-1}}{R_j}$. This determines the numerator and denominator of the rational function $a_j+{\mathcal {T}}_{j+1}$, and explains why we have $\prod _{j=1}^r(a_j+{\mathcal {T}}_{j+1})= \frac {R_0}{R_r}\prod _{j=1}^rb_{j}=r!s_m(r)$. This is different from, but reminiscent of, the ratio $p_{j+1}/p_j$ described on p. 26 of [Reference Olds8]. $\diamond$

Corollary 2.2 If $r,\,m\in {\mathbb {Z}}$ and $0< r< m$, then

\[ s_m(r):=\sum_{i=0}^r\binom{m}{i} =\frac{(r+1)\binom{m}{r+1}}{m-2r+{\mathcal{T}}_1} \quad\text{where } {\mathcal{T}}_1={\vcenter{\hbox{ $\mathcal{K}$}}}_{i=1}^r\frac{2i(r+1-i)}{m-2r+3i}>0. \]

If $r=0$, then $s_m(r)=\frac {(r+1)\binom{m}{r+1}}{m-2r+{\mathcal {T}}_1}$ is true, but ${\mathcal {T}}_1=\mathcal{K}_{i=1}^r\frac {2i(r+1-i)}{m-2r+3i}=0$.

We will need some additional tools such as proposition 2.3 and corollary 2.4 below in order to prove theorem 1.3.

Since $s_m(m-r)=2^m-s_m(r-1)$ approximating $s_m(r)$ for $0\leqslant r\leqslant m$ reduces to approximating $s_m(r)$ for $0\leqslant r\leqslant \lfloor \frac {m}{2}\rfloor$. Hence the hypothesis $r<\frac {m+3}{2}$ in proposition 2.3 and corollary 2.4 is not too restrictive. Proposition 2.3 generalizes [Reference Olds8, Theorem 3.3].

Let ${\mathcal {H}}_j:=\mathcal{K}_{i=1}^j\frac {b_i}{a_i}$ denote the $j$th head of the fraction $\mathcal{K}_{i=1}^r\frac {b_i}{a_i}$, where ${\mathcal {H}}_0=0$.

Proposition 2.3 Let $b_i=2i(r+1-i)$ and $a_i=m-2r+3i$ for $0\leqslant i\leqslant r$. If $r<\frac {m+3}{2}$, then $a_0+{\mathcal {H}}_r=\frac {(r+1)\binom{m}{r+1}}{s_m(r)}$ can be approximated using the following chain of inequalities

\begin{align*} a_0+{\mathcal{H}}_0< a_0+{\mathcal{H}}_2<\cdots< a_0+{\mathcal{H}}_{2\lfloor r/2\rfloor} <& a_0+{\mathcal{H}}_{2\lfloor (r-1)/2\rfloor+1}<\\& \cdots< a_0+{\mathcal{H}}_3< a_0+{\mathcal{H}}_1. \end{align*}

Proof. Note that $r$ equals either $2\lfloor r/2\rfloor$ or $2\lfloor (r-1)/2\rfloor +1$, depending on its parity.

We showed in the proof of theorem 1.1 that $\frac {(r+1)\binom{m}{r+1}}{s_m(r)}=a_0+{\mathcal {H}}_r=a_0+\mathcal{K}_{i=1}^r\frac {b_i}{a_i}$. Since $r<\frac {m+3}{2}$, we have $a_i>0$ and $b_i>0$ for $1\leqslant i\leqslant r$ and hence $\frac {b_i}{a_i}>0$. A straightforward induction (which we omit) depending on the parity of $r$ proves that ${\mathcal {H}}_0<{\mathcal {H}}_2<\cdots <{\mathcal {H}}_{2\lfloor r/2\rfloor }<{\mathcal {H}}_{2\lfloor (r-1)/2\rfloor +1}<\cdots <{\mathcal {H}}_3<{\mathcal {H}}_1$. For example, if $r=3$, then

\[ {\mathcal{H}}_0=0<\frac{b_1}{a_1 +\dfrac{b_2}{a_2}} < \frac{b_1}{a_1 +\dfrac{b_2}{a_2 +\dfrac{b_3}{a_3}}} < \frac{b_1}{a_1}={\mathcal{H}}_1. \]

proves ${\mathcal {H}}_0<{\mathcal {H}}_2<{\mathcal {H}}_3<{\mathcal {H}}_1$ as the tails are positive. Adding $a_0$ proves the claim.

In asking whether $g_{\omega,m}(r)$ is a unimodal function, it is natural to consider the ratio $g_{\omega,m}(r+1)/g_{\omega,m}(r)$ of successive terms. This suggests defining

(2.3)\begin{equation} t(r)=t_{m}(r):= \frac{s_m(r+1)}{s_m(r)}=1+\frac{\binom{m}{r+1}}{s_m(r)}=1+\frac{Q}{r+1}. \end{equation}

We will prove in lemma 3.1 that $t(r)$ is a strictly decreasing function that determines when $g_{\omega,m}(r)$ is increasing or decreasing, and $t_{m}(r_0-1)\geqslant \omega >t_{m}(r_0)$ determines $r_0$.

Corollary 2.4 We have $m-2r\leqslant \frac {(r+1)\binom{m}{r+1}}{s_m(r)}$ for $r\geqslant 0$, and

\[ \frac {(r+1)\binom{m}{r+1}}{s_m(r)}\leqslant m-2r+\frac {2r}{m-2r+3}\quad{\rm for}\quad 0\leqslant r<\frac{m+3}{2}. \]

Hence $\frac {m+2}{r+1}\leqslant t_m(r)+1$ for $r\geqslant 0$, and

\[ \frac{m+2}{r+1}\leqslant t_m(r)+1\leqslant\frac{m+2}{r+1}+\frac{2r}{(r+1)(m-2r+3)} \quad\text{for $0\leqslant r<\frac{m+3}{2}$.} \]

Also $\frac {m+2}{r+1}< t_m(r)+1$ for $r>0$, and the above upper bound is strict for $1< r<\frac {m+3}{2}$.

Proof. We proved $Q=\frac {(r+1)\binom{m}{r}}{s_m(r)}=(m-2r)+\mathcal{K}_{i=1}^r\frac {2i(r+1-i)}{m-2r+3i}$ in theorem 1.1. Hence $m-2r=\frac {(r+1)\binom{m}{r+1}}{s_m(r)}$ if $r=0$ and $m-2r<\frac {(r+1)\binom{m}{r+1}}{s_m(r)}$ if $1\leqslant r<\frac {m+3}{2}$ by proposition 2.3. Clearly $m-2r<0\le \frac {(r+1)\binom{m}{r+1}}{s_m(r)}$ if $\frac {m+3}{2}\le r\le m$. Similarly $\frac {(r+1)\binom{m}{r+1}}{s_m(r)}= m-2r+\frac {2r}{m-2r+3}$ if $r=0,\,1$, and again proposition 2.3 shows that ${\frac {(r+1)\binom{m}{r+1}}{s_m(r)}< m-2r+\frac {2r}{m-2r+3}}$ if $1< r<\frac {m+3}{2}$. The remaining inequalities (and equalities) follow similarly since $t_m(r)+1=2+\frac {\binom{m}{r+1}}{s_m(r)}$ and $2+\frac {m-2r}{r+1}=\frac {m+2}{r+1}$.

3. Estimating the maximizing input $r_0$

Fix $\omega >1$. In this section we consider the function $g(r)=g_{\omega,m}(r)$ given by (1.1). As seen in table 1, it is easy to compute $g(r)$ if $r$ is near $0$ or $m$. For $m$ large and $r$ near $0$, we have ‘sub-exponential’ growth $g(r)\approx \frac {m^r}{r!\omega ^r}$. Similarly for $r$ near $m$, we have exponential decay $g(r)\approx \frac {2^m}{\omega ^r}$. The middle values require more thought.

Table 1. Values of $g_{w,m}(r)$

On the other hand, the plots $y=g(r)$, $0\leqslant r\leqslant m$, exhibit a remarkable visual symmetry when $m$ is large. The relation $s_m(m-r)=2^m-s_m(r-1)$ and the distorting scale factor of $\omega ^{-r}$ shape the plots. The examples in figure 1 show an approximate left–right symmetry about a maximizing input $r\approx \frac {m}{\omega +1}$. It surprised the authors that in many cases there exists a simple exact formula for the maximizing input (it is usually unique as corollary 3.2 suggests). In figure 1 we have used different scale factors for the $y$-axes. The maximum value of $g_{\omega,m}(r)$ varies considerably as $\omega$ varies (c.f. lemma 5.1), so we scaled the maxima (rounded to the nearest integer) to the same height.

Lemma 3.1 Recall that $g(r)=\omega ^{-r} s_m(r)$ by (1.1) and $t(r)=\frac {s_m(r+1)}{s_m(r)}$ by (2.3).

  1. (a) $t(r-1)>t(r)>\frac {m-r}{r+1}$ for $0\leqslant r\leqslant m$ where $t(-1):=\infty$;

  2. (b) $g(r)< g(r+1)$ if and only if $t(r)>\omega$;

  3. (c) $g(r)\leqslant g(r+1)$ if and only if $t(r)\geqslant \omega$;

  4. (d) $g(r)> g(r+1)$ if and only if $\omega > t(r)$;

  5. (e) $g(r)\geqslant g(r+1)$ if and only if $\omega \geqslant t(r)$;

  6. (f) if $\omega >1$ then some $r_0\in \{0,\,\ldots,\,m\}$ satisfies $t(r_0-1)\geqslant \omega > t(r_0)$, and this condition is equivalent to

    \[ g(0)<\cdots < g(r_0-1)\leqslant g(r_0) \quad {\rm and}\quad g(r_0)>\cdots >g(m). \]

Proof. (a) We prove, using induction on $r$, that $t(r-1)>t(r)>\binom{m}{r+1}/\binom{m}{r}$ holds for $0\leqslant r\leqslant m$. These inequalities are clear for $r=0$ as $\infty >m+1>m$. For real numbers $\alpha,\,\beta,\,\gamma,\,\delta >0$, we have $\alpha \delta -\beta \gamma >0$ if and only if $\frac {\alpha }{\beta }>\frac {\alpha +\gamma }{\beta +\delta }>\frac {\gamma }{\delta }$; that is, the mediant $\frac {\alpha +\gamma }{\beta +\delta }$ of $\frac {\alpha }{\beta }$ and $\frac {\gamma }{\delta }$ lies strictly between $\frac {\alpha }{\beta }$ and $\frac {\gamma }{\delta }$. If $0< r\leqslant m$, then by induction

\[ t(r-1)>\frac{\binom{m}{r}}{\binom{m}{r-1}} =\frac{m-r+1}{r}>\frac{m-r}{r+1}=\frac{\binom{m}{r+1}}{\binom{m}{r}}. \]

Applying the ‘mediant sum’ to $t(r-1)=\frac {s_m(r)}{s_m(r-1)}>\frac {\binom{m}{r+1}}{\binom{m}{r}}$ gives

\[ \frac{s_m(r)}{s_m(r-1)}>\frac{s_m(r)+\binom{m}{r+1}}{s_m(r-1)+\binom{m}{r}} =\frac{s_m(r+1)}{s_m(r)}=t(r) >\frac{\binom{m}{r+1}}{\binom{m}{r}}. \]

Therefore $t(r-1)>t(r)>\binom{m}{r+1}/\binom{m}{r}=\frac {m-r}{r+1}$ completing the induction, and proving (a).

(b,c,d,e) The following are equivalent: $g(r)< g(r+1)$; $\omega s_m(r)< s_m(r+1)$; and $\omega < t(r)$. The other claims are proved similarly by replacing < with $\leqslant$, >, $\geqslant$.

(f) Observe that $t(m)=\frac {s_m(m+1)}{s_m(m)}=\frac {2^m}{2^m}=1$. By part (a), the function $y=t(r)$ is decreasing for $-1\leqslant r\leqslant m$. Since $\omega >1$, there exists an integer $r_0\in \{0,\,\ldots,\,m\}$ such that $\infty =t(-1)>\cdots >t(r_0-1)\geqslant \omega > t(r_0)>\cdots > t(m)=1$. By parts (b,c,d,e) an equivalent condition is $g(0)<\cdots < g(r_0-1)\leqslant g(r_0)$ and $g(r_0)>\cdots >g(m)$.

The following is an immediate corollary of lemma 3.1(f).

Corollary 3.2 If $t(r_0-1)>\omega$, then the function $g(r)$ in (1.1) has a unique maximum at $r_0$. If $t(r_0-1)=\omega$, then $g(r)$ has two equal maxima, one at $r_0-1$ and one at $r_0$.

As an application of theorem 1.1 we show that the largest maximizing input $r_0$ for $g_{\omega,m}(r)$ satisfies $\lfloor \frac {m+2}{\omega +1}\rfloor \leqslant r_0$. There are at most two maximizing inputs by corollary 3.2.

Lemma 3.3 Suppose that $\omega >1$ and $m\in {\mathbb {Z}}$, $m\geqslant 0$. If $r':=\lfloor \frac {m+2}{\omega +1}\rfloor$, then

\[ g(-1)< g(0)<\dots < g(r'-1)\leqslant g(r'),\quad {\rm and}\quad g(-1)<\dots < g(r'-1)< g(r') \]

if $r'>1$ or $\omega \ne m+1$.

Proof. The result is clear when $r'=0$. If $r'=1$, then $r'\leqslant \frac {m+2}{\omega +1}$ gives $\omega \leqslant m+1$ or $g(0)\leqslant g(1)$. Hence $g(0)< g(1)$ if $\omega \ne m+1$. Suppose that $r'>1$. By lemma 3.1(c,f) the chain $g(0)<\dots < g(r')$ is equivalent to $g(r'-1)< g(r')$, that is $t(r'-1)> \omega$. However, $t(r'-1)+1>\frac {m+2}{r'}$ by corollary 2.4 and $r'\leqslant \frac {m+2}{\omega +1}$ implies $\frac {m+2}{r'}\geqslant \omega +1$. Hence $t(r'-1)+1>\omega +1$, so that $t(r'-1)> \omega$ as desired.

Proof Proof of theorem 1.4

Suppose that $\omega \in \{3,\,4,\,\ldots \}$. Then $g(0)<\dots < g(r'-1)\leqslant g(r')$ by lemma 3.3 with strictness when $\omega \ne m+1$. If $\omega =m+1$, then $r'=\lfloor \frac {m+2}{\omega +1}\rfloor =1$ and $g(0)=g(1)$ as claimed. It remains to show that $g(r')>g(r'+1)>\cdots >g(m)$. However, we need only prove that $g(r')> g(r'+1)$ by lemma 3.1(f), or equivalently $\omega > t(r')$ by lemma 3.1(d).

Clearly $\omega \geqslant 3$ implies $r'\leqslant \frac {m+2}{\omega +1}\leqslant \frac {m+2}{4}$. As $0\leqslant r'<\frac {m+3}{2}$, corollary 2.4 gives

\[ \frac{m+2}{r'+1}+\frac{2r'}{(r'+1)(m-2r'+3)}\geqslant t(r')+1. \]

Hence $\omega +1> t(r')+1$ holds if $\omega +1> \frac {m+2}{r'+1}+\frac {2r'}{(r'+1)(m-2r'+3)}$. Since $\omega +1$ is an integer, we have $m+2=r'(\omega +1)+c$ where $0\leqslant c\leqslant \omega$. It follows from $0\leqslant r'\leqslant \frac {m+2}{4}$ that $\frac {2r'}{m-2r'+3}<1$. This inequality and $m+2\leqslant r'(\omega +1)+\omega$ gives

\[ m+2+\frac{2r'}{m-2r'+3}< r'(\omega+1)+\omega+1=(r'+1)(\omega+1). \]

Thus $\omega +1>\frac {m+2}{r'+1}+\frac {2r'}{(r'+1)(m-2r'+3)}\geqslant t(r')+1$, so $\omega >t(r')$ as required.

Remark 3.4 The proof of theorem 1.4 can be adapted to the case $\omega =2$. If $m+2=3r'+c$ where $c\leqslant \omega -1=1$, then $\frac {2r'}{m-2r'+3}=\frac {2r'}{r'+c+1}<2$, and if $c=\omega =2$, then a sharper ${\mathcal {H}}_2$-bound must be used. This leads to a much shorter proof than [Reference Glasby and Paseman4, Theorem 1.1]. $\diamond$

4. Non-integral values of $\omega$

In this section, we prove that the maximum value of $g(r)$ is $g(r')$ or $g(r'+1)$ if $\omega \geqslant \sqrt {3}$. Before proving this result (theorem 1.3), we shall prove two preliminary lemmas.

Lemma 4.1 Suppose that $\omega >1$ and $r':=\lfloor \frac {m+2}{\omega +1}\rfloor$. If $\frac {m+2}{r'+1}\geqslant \sqrt {3}+1$, then

\[ g({-}1)< g(0)<\cdots< g(r'-1)\leqslant g(r'), \quad\text{and}\quad g(r'+1)>g(r'+2)>\cdots>g(m). \]

Proof. It suffices, by lemma 3.1(f) and lemma 3.3 to prove that $g(r'+1)>g(r'+2)$. The strategy is to show $\omega >t(r'+1)$, that is $\omega +1>t(r'+1)+1$. However, $\omega +1>\frac {m+2}{r'+1}$, so it suffices to prove that $\frac {m+2}{r'+1}\geqslant t(r'+1)+1$. Since $r'+1\leqslant \frac {m+2}{\sqrt {3}+1}<\frac {m+2}{2}$, we can use corollary 2.4 and just prove that $\frac {m+2}{r'+1}\geqslant \frac {m+2}{r'+2}+\frac {2r'+2}{(r'+2)(m-2r'+1)}$. This inequality is equivalent to $\frac {m+2}{r'+1}\geqslant \frac {2r'+2}{m-2r'+1}$. However, $\frac {m+2}{r'+1}\geqslant \sqrt {3}+1$, so we need only show that $\sqrt {3}+1\geqslant \frac {2(r'+1)}{m-2r'+1}$, or equivalently $m-2r'+1\geqslant (\sqrt {3}-1)(r'+1)$. This is true since $\frac {m+2}{r'+1}\geqslant \sqrt {3}+1$ implies $m-2r'+1\geqslant (\sqrt {3}-1)r'+\sqrt {3}>(\sqrt {3}-1)(r'+1)$.

Remark 4.2 The strict inequality $g(r'-1)< g(r')$ holds by lemma 3.3 if $r'>1$ or $\omega \ne m+1$. It holds vacuously for $r'=0$. Hence adding the additional hypothesis that $\omega \ne m+1$ if $r'=1$ to lemma 4.1 (and theorem 1.3), we may conclude that the inequality $g(r'-1)\leqslant g(r')$ is strict.

Remark 4.3 In lemma 4.1, the maximum can occur at $r'+1$. If $\omega =2.5$ and $m=8$, then $r'=\lfloor \frac {10}{3.5}\rfloor =2$ and $\frac {m+2}{r'+1}=\frac {10}{3}\geqslant \sqrt {3}+1$ however $g_{2.5,8}(2)=\frac {740}{125}< \frac {744}{125}=g_{2.5,8}(3)$. $\diamond$

Remark 4.4 The gap between $r'$ and the largest maximizing input $r_0$ can be arbitrarily large if $\omega$ is close to 1. For $\omega >1$, we have $r'=\lfloor \frac {m+2}{\omega +1}\rfloor <\frac {m+2}{2}$. If $1<\omega \leqslant \frac {1}{1-2^{-m}}$, then $g(m-1)\leqslant g(m)$, so $r_0=m$. Hence $r_0-r'>\frac {m-2}{2}$.

Remark 4.5 Since $r'\leqslant \lfloor \frac {m+2}{\omega +1}\rfloor < r'+1$, we see that $r'+1\approx \frac {m+2}{\omega +1}$, so that $\frac {m+2}{r'+1}\approx \omega +1$. Thus lemma 4.1 suggests that if $\omega \gtrsim \sqrt {3}$, then $g_{\omega,m}(r)$ may have a maximum at $r'$ or $r'+1$. This heuristic reasoning is made rigorous in theorem 1.3. $\diamond$

Remark 4.6 Theorem 1.1 can be rephrased as $t_m(r)=\frac {s_m(r+1)}{s_m(r)}=\frac {m-r+1}{r+1}+\frac {{\mathcal {K}}_m(r)}{r+1}$ where

(4.1)\begin{equation} {\mathcal{K}}_m(r)=\mathop{\vcenter{\hbox{ $\mathcal{K}$}}}_{i=1}^{r} \frac{2i(r+1-i)}{m-2r+3i}= \frac{\displaystyle 2r}{\displaystyle m-2r+3 +\frac{\displaystyle 4r-4}{\displaystyle m-2r+6 +\frac{\displaystyle 6r-12}{\llap{{\ddots}} {{\displaystyle m+r-3 + \frac{2r}{m+r}}}}}}. \end{equation}

The following lemma repeatedly uses the expression $\omega >t_m(r+1)$. This is equivalent to $\omega >\frac {m-r}{r+2}+\frac {{\mathcal {K}}_m(r+1)}{r+2}$, that is $(\omega +1)(r+2)>m+2+{\mathcal {K}}_m(r+1)$. $\diamond$

Lemma 4.7 Let $m\in \{0,\,1,\,\ldots \}$ and $r'=\lfloor \frac {m+2}{\omega +1}\rfloor$. If any of the following three conditions are met, then $g_{\omega,m}(r'+1)>\cdots >g_{\omega,m}(m)$ holds: (a) $\omega \geqslant 2$, or  (b) $\omega \geqslant \frac {1+\sqrt {97}}{6}$ and $r'\ne 2$, or  (c) $\omega \geqslant \sqrt {3}$ and $r'\not \in \{2,\,3\}$.

Proof. The conclusion $g_{\omega,m}(r'+1)>\cdots >g_{\omega,m}(m)$ holds trivially if $r'+1\geqslant m$. Suppose henceforth that $r'+1< m$. Except for the excluded values of $r',\,\omega$, we will prove that $g_{\omega,m}(r'+1)>g_{\omega,m}(r'+2)$ holds, as this implies $g_{\omega,m}(r'+1)>\cdots >g_{\omega,m}(m)$ by lemma 3.1(f). Hence we must prove that $\omega >t_m(r'+1)$ by lemma 3.1(d).

Recall that $r'\leqslant \frac {m+2}{\omega +1}< r'+1$. If $r'=0$, then $m+2<\omega +1$, that is $\omega >m+1>t(1)$ as desired. Suppose now that $r'=1$. There is nothing to prove if $m=r'+1=2$. Assume that $m>2$. Since $m+2<2(\omega +1)$, we have $2< m<2\omega$. The last line of remark 4.6 and (4.1) give the desired inequality:

\[ \omega>\frac{m}{2}\geqslant\frac{m-1}{3}+\frac{4}{3\left(m-1+\dfrac{4}{m+2}\right)}=t_m(2). \]

In summary, $g_{\omega,m}(r'+1)>\cdots >g_{\omega,m}(m)$ holds for all $\omega >1$ if $r'\in \{0,\,1\}$.

We next prove $g_{\omega,m}(r'+1)>g_{\omega,m}(r'+2)$, or equivalently $\omega >t_m(r'+1)$ for $r'$ large enough, depending on $\omega$. We must prove that $(\omega +1)(r'+2)>m+2+\mathcal{K}_m(r'+1)$ by remark 4.6. Writing $m+2=(\omega +1)(r'+\varepsilon )$ where $0\leqslant \varepsilon <1$, our goal, therefore, is to show $(\omega +1)(2-\varepsilon )>{\mathcal {K}}_m(r'+1)$. Using (4.1) gives

\[ {\mathcal{K}}_m(r'+1)=\frac{2(r'+1)}{m-2(r'+1)+3+{\mathcal{T}}} =\frac{2(r'+1)}{(\omega+1)(r'+\varepsilon)-2(r'+1)+1+{\mathcal{T}}} \]

where ${\mathcal {T}}>0$ by theorem 1.1 as $r'>0$. Rewriting the denominator using

\[ (\omega+1)(r'+\varepsilon)-2(r'+1)=(\omega-1)(r'+1)-(\omega+1)(1-\varepsilon), \]

our goal $(\omega +1)(2-\varepsilon )>{\mathcal {K}}_m(r'+1)$ becomes

\[ (\omega+1)(2-\varepsilon)\left[(\omega-1)(r'+1)-(\omega+1)(1-\varepsilon)+1+{\mathcal{T}}\right] >2(r'+1). \]

Dividing by $(2-\varepsilon )(r'+1)$ and rearranging gives

\[ (\omega^2-1)+\frac{(\omega+1)(1+{\mathcal{T}})}{r'+1}>\frac{2}{2-\varepsilon} +\frac{(\omega+1)^2(1-\varepsilon)}{r'+1}. \]

This inequality may be written $(\omega ^2-1)+\lambda >\frac {2}{2-\varepsilon }+\mu (1-\varepsilon )$ where $\lambda =\frac {(\omega +1)(1+{\mathcal {T}})}{r'+1}>0$ and $\mu =\frac {(\omega +1)^2}{r'+1}>0$. We view $f(\varepsilon ):=\frac {2}{2-\varepsilon }+\mu (1-\varepsilon )$ as a function of a real variable $\varepsilon$ where $0\leqslant \varepsilon <1$. However, $f(\varepsilon )$ is concave as the second derivative $f''(\varepsilon )=\frac {4}{(2-\varepsilon )^3}$ is positive for $0\leqslant \varepsilon <1$. Hence the maximum value occurs at an end point: either $f(0)=1+\mu$ or $f(1)=2$. Therefore, it suffices to prove that $(\omega ^2-1)+\lambda >\max \{2,\,1+\mu \}$.

If $2\geqslant 1+\mu$, then the desired bound $(\omega ^2-3)+\lambda >0$ holds as $\omega \geqslant \sqrt {3}$. Suppose now that $2<1+\mu$. We must show $(\omega ^2-1)+\lambda >1+\mu$, that is $\omega ^2-2>\mu -\lambda =\frac {(\omega +1)(\omega -{\mathcal {T}})}{r'+1}$. Since ${\mathcal {T}}>0$, a stronger inequality (that implies this) is $\omega ^2-2\geqslant \frac {(\omega +1)\omega }{r'+1}$. The (equivalent) quadratic inequality $r'\omega ^2-\omega -2(r'+1)\geqslant 0$ in $\omega$ is true provided $\omega \geqslant \frac {1+\sqrt {1+8r'(r'+1)}}{2r'}$. This says $\omega \geqslant 2$ if $r'=2$, and $\omega \geqslant \frac {1+\sqrt {97}}{6}$ if $r'=3$. If $r'\geqslant 4$, we have

\[ \frac{1+\sqrt{1+8r'(r'+1)}}{2r'}= \frac{1}{2r'}+\sqrt{\frac{1}{4(r')^2}+2\left(1+\frac{1}{r'}\right)} \leqslant\frac{1}{8}+\sqrt{\frac{1}{64}+\frac{5}{2}}<\sqrt{3}. \]

The conclusion now follows from the fact that $2>\frac {1+\sqrt {97}}{6} >\sqrt {3}$.

Proof Proof of theorem 1.3

By lemma 4.1 it suffices to show that $g(r'+1)>g(r'+2)$ holds when $r'+1< m$ and $\omega \geqslant \sqrt {3}$. By lemma 4.7(a), we can assume that $\sqrt {3}\leqslant \omega <2$ and $r'\in \{2,\,3\}$. For these choices of $\omega$ and $r'$, we must show that $\omega >t_m(r'+1)$ by lemma 3.1 for all permissible choices of $m$. Since $(\omega +1)r'\leqslant m+2<(\omega +1)(r'+1)$, when $r'=2$ we have $5<2(\sqrt {3}+1)\leqslant m+2<9$ so that $4\leqslant m\leqslant 6$. However, $t_m(3)$ equals $\tfrac {16}{15},\,\tfrac {31}{26},\,\tfrac {19}{14}$ for these values of $m$. Thus $\sqrt {3}>t_m(3)$ holds as desired. Similarly, if $r'=3$, then $8<3(\sqrt {3}+1)\leqslant m+2<12$ so that $7\leqslant m\leqslant 9$. In this case $t_m(4)$ equals $\tfrac {40}{33},\,\tfrac {219}{163},\,\tfrac {191}{128}$ for these values of $m$. In each case $\sqrt {3}>t_m(4)$, so the proof is complete.

Remark 4.8 We place remark 4.4 in context. The conclusion of theorem 1.3 remains true for values of $\omega$ smaller than $\sqrt {3}$ and not ‘too close to 1’ and $m$ is ‘sufficiently large’. Indeed, by adapting the proof of lemma 4.7 we can show there exists a sufficiently large integer $d$ such that $m > d^4$ and $\omega > 1 + \frac {1}{d}$ implies $g(r'+d) > g(r'+d+1)$. This shows that $r' \leqslant r_0 \leqslant r' +d$, so $r_0-r'\leqslant d$. We omit the technical proof of this fact. $\diamond$

Remark 4.9 The sequence, $a_0+{\mathcal {H}}_1,\,\ldots,\,a_0+{\mathcal {H}}_r$ terminates at $\frac {r+1}{s_m(r)}\binom{m}{r+1}$ by theorem 1.1. We will not comment here on how quickly the alternating sequence in proposition 2.3 converges when $r<\frac {m+3}{2}$. If $r=m$, then $a_0=-m$ and $\frac {m+1}{s_m(m+1)}\binom{m}{m+1}=0$, so theorem 1.1 gives the curious identity ${\mathcal {H}}_m=\mathcal{K}_{i=1}^m\frac {2i(m+1-i)}{3i-m}=m$. If $\omega$ is less than $\sqrt {3}$ and ‘not too close to 1’, then we believe that $r_0$ is approximately $\lfloor \frac {m+2}{\omega +1}+ \frac {2}{\omega ^2 -1}\rfloor$, c.f. remark 4.8.

5. Estimating the maximum value of $g_{\omega,m}(r)$

In this section we relate the size of the maximum value $g_{\omega,m}(r_0)$ to the size of the binomial coefficient $\binom{m}{r_0}$. In the case that we know a formula for a maximizing input $r_0$, we can readily estimate $g_{\omega,m}(r_0)$ using approximations, such as [Reference Stănică10], for binomial coefficients.

Lemma 5.1 The maximum value $g_{\omega,m}(r_0)$ of $g_{\omega,m}(r)$, $0\leqslant r\leqslant m$, satisfies

\[ \frac{1}{(\omega-1)\omega^{r_0}}\binom{m}{r_0+1} < g_{\omega,m}(r_0) \leqslant \frac{1}{(\omega-1)\omega^{r_0-1}}\binom{m}{r_0}. \]

Proof. Since $g(r_0)$ is a maximum value, we have $g(r_0-1)\leqslant g(r_0)$. This is equivalent to $(\omega -1)s_m(r_0-1)\leqslant \binom{m}{r_0}$ as $s_m(r_0)=s_m(r_0-1)+\binom{m}{r_0}$. Adding $(\omega -1)\binom{m}{r_0}$ to both sides gives the equivalent inequality $(\omega -1) s_m(r_0)\leqslant \omega \binom{m}{r_0}$. This proves the upper bound.

Similar reasoning shows that the following are equivalent: (a) $g(r_0)> g(r_0+1)$; (b) $(\omega -1)s_m(r_0)> \binom{m}{r_0+1}$; and (c) $g_{\omega,m}(r_0)>\frac {1}{(\omega -1)\omega ^{r_0}}\binom{m}{r_0+1}$.

In theorem 1.3 the maximizing input $r_0$ satisfies $r_0=r'+d$ where $d\in \{0,\,1\}$. In such cases when $r_0$ and $d$ are known, we can bound the maximum $g_{\omega,m}(r_0)$ as follows.

Corollary 5.2 Set $r' := \lfloor \frac {m+2}{\omega +1}\rfloor$ and $k := m+2 - (\omega +1)r'$. Suppose that $r_0 = r'+d$ and $G=\frac {1}{(\omega -1)\omega ^{r_0-1}}\binom{m}{r_0}$. Then

\[ 0\leqslant k< \omega +1, d\geqslant 0\quad {\rm and}\quad 1-\frac {1+d-\frac {d+2-k}{\omega }}{r_0+1} <\frac {g_{\omega,m}(r_0)}{G} \leqslant 1. \]

Proof. By lemma 3.3, $r_0 = r'+d$ where $d\in \{0,\,1,\,\ldots \}$. Since $r' = \lfloor \frac {m+2}{\omega +1}\rfloor$, we have $m+2 = (\omega +1)r'+k$ where $0\leqslant k< \omega +1$. The result follows from lemma 5.1 and $m = (\omega +1)(r_0-d)+k-2$ as $\binom{m}{r_0+1}=\frac {m-r_0}{r_0+1}\binom{m}{r_0}$ and $\frac {m-r_0}{r_0+1}$ equals

\[ \frac{\omega(r_0-d)-d+k-2}{r_0+1} =\omega-\frac{\omega+\omega d+d+2-k}{r_0+1} =\omega\left(1-\frac{1+d+\frac{d+2-k}{\omega}}{r_0+1}\right). \]

The following remark is an application of the Chernoff bound, c.f. [Reference Worsch11, Section 4]. Unlike theorem 1.1, it requires the cumulative distribution function $\Phi (x)$, which is a non-elementary integral, to approximate $s_m(r)$. It seems to give better approximations only for values of $r$ near $\frac {m}{2}$, see remark 5.4.

Remark 5.3 We show how the Berry–Esseen inequality for a sum of binomial random variables can be used to approximate $s_m(r)$. Let $B_1,\,\ldots,\,B_m$ be independent identically distributed binomial variables with a parameter $p$ where $0< p<1$, so that $P(B_i=1)=p$ and $P(B_i=0)=q:= 1-p$. Let $X_i:= B_i-p$ and $X:=\frac {1}{\sqrt {mpq}}(\sum _{i=1}^m X_i)$. Then

\[ E(X_i)=E(B_i)-p=0,\quad E(X_i^2)=pq,\quad {\rm and}\quad E(|X_i|^3)=pq(p^2+q^2). \]

Hence $E(X)=\frac {1}{\sqrt {mpq}}(\sum _{i=1}^m E(X_i))=0$ and $E(X^2)=\frac {1}{mpq}(\sum _{i=1}^m E(X_i^2))=1$. By [Reference Nagaev and Chebotarev7, Theorem 2] the Berry–Esseen inequality applied to $X$ states that

\begin{align*} |P(X\leqslant x)-\Phi(x)|& \leqslant\frac{Cpq(p^2+q^2)}{(pq)^{3/2}\sqrt{m}} \\ & =\frac{C(p^2+q^2)}{\sqrt{mpq}} \quad\text{for all } m\in\{1,2,\ldots\} \text{ and } x\in{\mathbb{R}}, \end{align*}

where the constant $C:= 0.4215$ is close to the lower bound $C_0=\frac {10+\sqrt {3}}{6\sqrt {2\pi }}=0.4097\cdots$ and $\Phi (x)=\frac {1}{\sqrt {2\pi }}\int _{-\infty }^x e^{-t^2/2}\,dt=\frac {1}{2}\left (1+{\rm erf}\left (\frac {x}{\sqrt {2}}\right )\right )$ is the cumulative distribution function for standard normal distribution.

Writing $B=\sum _{i=1}^mB_i$ we have $P(B\leqslant b)=\sum _{i=0}^{\lfloor b\rfloor }\binom{m}{i}p^iq^{m-i}$ for $b\in {\mathbb {R}}$. Thus $X=\frac {B-mp}{\sqrt {mpq}}$ and $x=\frac {b-mp}{\sqrt {mpq}}$ satisfy

\[ \left|P(B\leqslant b)-\Phi\left(\frac{b-mp}{\sqrt{mpq}}\right)\right| \leqslant\frac{C(p^2+q^2)}{\sqrt{mpq}} \quad\text{for all $m\in\{1,\,2,\,\ldots\}$ and $b\in{\mathbb{R}}$} .\]

Setting $p=q=\tfrac {1}{2}$, and taking $b=r\in \{0,\,1,\,\ldots,\,m\}$ shows

\[ \left|2^{{-}m}s_m(r)-\Phi\left(\frac{2r-m}{\sqrt{m}}\right)\right| \leqslant\frac{0.4215}{\sqrt{m}} \quad\text{for } m\in\{1,2,\ldots\}. \]

Remark 5.4 Let $a_0+{\mathcal {H}}_k$ be the generalized continued fraction approximation to $\frac {(r+1)\binom{m}{r+1}}{s_m(r)}$ suggested by theorem 1.1, where ${\mathcal {H}}_k:=\mathcal{K}_{i=1}^k\frac {b_i}{a_i}$, and $k$ is the depth of the generalized continued fraction. We compare the following two quantities:

\[ e_{m,r,k}:= 1-\frac{(r+1)\binom{m}{r+1}}{(a_0+{\mathcal{H}}_k)s_m(r)} \quad\text{and}\quad E_{m,r}:=\left|1-\frac{2^m\Phi(\frac{2r-m}{\sqrt{m}})}{s_m(r)} \right| \leqslant\frac{0.4215\cdot 2^m}{\sqrt{m}\,s_m(r)}. \]

The sign of $e_{m,r,k}$ is governed by the parity of $k$ by proposition 2.3. We shall assume that $r\leqslant \frac {m}{2}$. As $\frac {2^m}{s_m(r)}$ ranges from $2^m$ to about 2 as $r$ ranges from 0 to $\lfloor \frac {m}{2}\rfloor$, it is clear that the upper bound for $E_{m,r}$ will be huge unless $r$ satisfies $\frac {m-\varepsilon }{2}\le r\le \frac {m}{2}$ where $\varepsilon$ is ‘small’ compared to $m$. By contrast, the computer code [Reference Glasby3] verifies that the same is true for $E_{m,r}$, and shows that $|e_{m,r,k}|$ is small, even when $k$ is tiny, when $0\le r<\frac {m-\varepsilon }{2}$, see table 2. Hence the ‘generalized continued fraction’ approximation to $s_m(r)$ is complementary to the ‘statistical’ approximation, as shown in table 2. The reader can extend table 2 by running the code [Reference Glasby3] written in the Magma [Reference Bosma, Cannon and Playoust1] language, using the online calculator http://magma.maths.usyd.edu.au/calc/, for example.

Table 2. Upper bounds for $|e_{m,r,k}|$ and $E_{m,r}$ for $m=10^4$

Acknowledgements

SPG received support from the Australian Research Council Discovery Project Grant DP190100450. GRP thanks his family, and SPG thanks his mother.

References

Bosma, Wieb, Cannon, John and Playoust, Catherine. The Magma algebra system. I. The user language. J. Symbolic Comput. 24 (1997), 235265, Computational algebra and number theory (London, 1993).CrossRefGoogle Scholar
Byun, S. H. and Poznanović, S.. On the maximum of the weighted binomial sum $(1+a)^{-r}\sum _{i=0}^r\binom{m}{i}a^i$. Discrete Math. 347 (2024), 113925.CrossRefGoogle Scholar
Glasby, S. P., Magma computer code for Remark 5.4, https://stephenglasby.github.io/BerryEsseenMagmaCode.Google Scholar
Glasby, S. P. and Paseman, G. R.. On the maximum of the weighted binomial sum $2^{-r}\sum _{i=0}^r\binom{m}{i}$. Electron. J. Combin. 29 (2022), article P2.5.CrossRefGoogle Scholar
Granville, Andrew, Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers. In Organic mathematics (Burnaby, BC, 1995), pp. 253–276. CMS Conf. Proc., Vol. 20 (Amer. Math. Soc., Providence, RI, 1997).Google Scholar
Ling, San and Xing, Chaoping. Coding theory. A first course (Cambridge University Press, Cambridge, 2004), xii+222 pp.CrossRefGoogle Scholar
Nagaev, S. V. and Chebotarev, V. I.. On the bound of proximity of the binomial distribution to the normal one. Theory Probab. Appl. 56 (2012), 213239.CrossRefGoogle Scholar
Olds, C. D.. Continued fractions (Random House, New York, 1963), viii+162 pp.CrossRefGoogle Scholar
Paseman, G., Poster ‘A continued fraction for a partial sum’, presented at the Short Communications Satellite 2022, concurrent with vICM2022. PDF found near https://scs-math.org/communications.Google Scholar
Stănică, P.. Good lower and upper bounds on binomial coefficients. JIPAM. J. Inequal. Pure Appl. Math. 2 (2001). Article 30.Google Scholar
Worsch, T., Lower and upper bounds for (sums of) binomial coefficients, www.researchgate.net/scientific-contributions/Thomas-Worsch-18934007.Google Scholar
Figure 0

Figure 1. Plots of $y=g_{\omega,24}(r)$ for $0\leqslant r\leqslant 24$ with $\omega \in \{1,\,\frac 32,\,2,\,3\}$, and $y=g_{3,12}(r)$

Figure 1

Table 1. Values of $g_{w,m}(r)$

Figure 2

Table 2. Upper bounds for $|e_{m,r,k}|$ and $E_{m,r}$ for $m=10^4$