# Argmax of weighted sum of binomials

(Writing my thesis, I encountered the following problem. It is secondary to the topic of the thesis and I have the solution that is enough for the purposes of the thesis—but inner perfectionist is still not happy.)

Fix two positive integers $n$ and $2 \leq \ell \leq n$ and define a discrete function $F : \{ 1, 2, \dotsc, n-\ell+1\} \rightarrow \mathbb N$ in the following way: $$F(w) = F_{n,\ell}(w) = w \sum_{i=0}^{\ell-1} \binom{n-w}{i} \,.$$

What is $\underset{w}{\operatorname{argmax}} F(w)$? I can prove (see below) that $$\underset{w}{\operatorname{argmax}} F(w) \in \left\{ \left\lfloor \frac{n+1}{\ell} \right\rfloor, \left\lceil \frac{n}{\ell} \right\rceil \right\}.$$ And though this result is efficient and easy to calculate, I somehow still want to see in some sense closed formula. Can you help me?

Proof. First of all, it is easy to see that $$\left\lfloor \frac{n+1}{\ell} \right\rfloor = \left\lceil \frac{n}{\ell} \right\rceil \quad\text{or}\quad \left\lfloor \frac{n+1}{\ell} \right\rfloor + 1 = \left\lceil \frac{n}{\ell} \right\rceil.$$ Then, to prove the statement, it is sufficient to show that $F(w)$ increases for $w < \left\lfloor \frac{n+1}{\ell} \right\rfloor$ and decreases for $w \geq \left\lceil \frac{n}{\ell} \right\rceil$.

Consider a finite difference: $$\Delta F(w) = F(w+1) - F(w) \,.$$

It can be expanded as follows: \begin{split} \Delta F(w) &= F(w+1) - F(w) \\ &= (w+1)\sum_{i=0}^{\ell-1}\binom{n-w-1}{i} - w\sum_{i=0}^{\ell-1}\binom{n-w}{i} \\ &= (w+1)\sum_{i=0}^{\ell-1}\binom{n-w-1}{i} - w\sum_{i=0}^{\ell-1}\left(\binom{n-w-1}{i} + \binom{n-w-1}{i-1}\right) \\ &= \sum_{i=0}^{\ell-1}\binom{n-w-1}{i} - w\sum_{i=0}^{\ell-1}\binom{n-w-1}{i-1} \,. \end{split}

We have: \begin{split} \Delta F(w) &= \sum_{i=0}^{\ell-1}\left( \binom{n-w-1}{i} - w\binom{n-w-1}{i-1} \right) \\ &= \sum_{i=0}^{\ell-1} \frac{(n-w-1)!}{i!(n-w-i)!}\left( n-i-w(i+1) \right) \,. \end{split} If we require that $$w \leq \frac{n-\ell+1}{\ell} = \frac{n+1}{\ell} - 1 \,,$$ then it follows also that $$w < \frac{n-i}{i+1} \quad \text{ for all } i < \ell-1 \,;$$ hence, each of the terms $(n-i-w(i+1))$ is positive for $i < \ell-1$ and $(n-\ell+1 - w\ell) \geq 0$. Therefore, $$F(1) < F(2) < \dotsb < F\left(\left\lfloor \frac{n+1}{\ell} - 1 \right\rfloor\right) < F\left(\left\lfloor \frac{n+1}{\ell} \right\rfloor\right) \,.$$

On the other hand, we can write: \begin{split} \Delta F(w) &= \sum_{i=0}^{\ell-1}\binom{n-w-1}{i} - w\sum_{i=0}^{\ell-1}\binom{n-w-1}{i-1} \\ &= \sum_{i=0}^{\ell-1}\binom{n-w-1}{i} - w\sum_{i=0}^{\ell-2}\binom{n-w-1}{i} \\ &= \binom{n-w-1}{\ell-1} + (1-w)\sum_{i=0}^{\ell-2}\binom{n-w-1}{i} \,. \end{split} And, if $w > 1$, we have: \begin{split} \Delta F(w) &< \binom{n-w-1}{\ell-1} + (1-w)\binom{n-w-1}{\ell-2} \\ &= \frac{(n-w-1)!}{(\ell-1)!(n-\ell-w+1)!} (n-w\ell) \,. \end{split}

If we further require $w \ge \frac{n}{\ell}$, then $\Delta F(w) < 0$ and $$F\left( \left\lceil \frac{n}{\ell} \right\rceil \right) > F\left( \left\lceil \frac{n}{\ell} \right\rceil +1 \right) > \dots > F(n-\ell+1) \,.$$

Let us write $S(m,l)= \sum^{l-1}_{i=0} \binom{m}{i}$, and use it only when $0\lt l \leq m$.
Note that $2S(m,l)= S(m+1,l) + \binom{m}{l-1}$, so if $2l \geq n$, then the maximum w is 2 by your argument and this relation.
Using the equation above and rearranging , $3S(m,l)= 2S(m+1,l) + 2\binom{m}{l-1} - S(m,l)$. This implies that $2S(m+1,l) \leq 3S(m,l)$ when $\binom{m}{l-1} \geq S(m,l-1)$. This latter condition occurs for some $l$ and $m$ with $2l \lt m \lt 3l$, but not all of them; as $m$ gets large and $2l$ approaches $m$ it can fail. This suggests to me that you will not find a nice characterization of your argmax, even if you restrict ceiling of $n/l$ to 3.