(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) \,. $$


1 Answer 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.

Gerhard "Small Cases Not Looking Good" Paseman, 2018.07.13.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.