3
$\begingroup$

I am looking for a proof for the following inequality:

$$ \sum_{j=0}^k {m k + m - 1\choose j} \leq 2^{m k} $$

I checked it numerically for all $m,k$ between 1 and 100. Here is a plot of the left-hand side divided by the right-hand side; the darkest tone (at the top and left) represents 1. The other tones are smaller. So I am quite sure this inequality is true. But how can I prove it?

enter image description here

$\endgroup$
2
$\begingroup$

Edit: I've changed the rules for how the switches operate according to Erel Segal-Halevi's suggestion; this should now be a full proof.

A combinatorial proof:

Suppose you have $mk$ lights, arranged in $m$ groups of $k$ lights each, and $mk + m-1$ switches. The first $mk$ switches are "normal" switches, and each toggles a single (unique) light; the last $m-1$ switches are "special" switches numbered $1$ through $m-1$, and the switch numbered $i$ toggles the entire group #$i$ as well as the entire group #$m$ (thus toggling a total of $2k$ lights).

All switches begin in the off position. You are allowed to move up to $k$ switches into the on position. How many different light patterns can you generate?

You have $\sum_{j=0}^k\binom{mk+m-1}{j}$ possible switch positions to generate. We need to convince ourselves that each switch position generates a unique light pattern. First, note that if we can determine from the light pattern exactly which special switches were flipped, we can determine the switch position. Thus it will be sufficient to determine which groups were turned on in virtue of the special switches (i.e., which special switches were flipped, plus group #$m$ iff an odd number of special switches were flipped).

We can make use of the following observation: given any pair of groups $i$ and $j$, if group $i$ was turned on by virtue of the special switches and group $j$ was not, then more lights are on in group $i$ than in group $j$. To show this to be true, note that if group $i$ was turned on by virtue of the special switches, at most $k-1$ normal switches have been flipped; letting $\ell_i$ denote the number of lights on in group $i$, if without the normal switches we had $\ell_i-\ell_j = k$, and each flip of a normal switch changes this quantity by at most $1$, then we have at the end of the process $\ell_i-\ell_j \geq k-(k-1) =1>0$.

We can also determine the number of groups turned on in virtue of the special switches. This is always an even number. Let this number be $2n$. If $n>0$, then $2nk$ lights are on, and at most $k-1$ individual switches remain, so the number of lights on is in the interval $[(2n-1)k+1, 2nk+k-1]$. If $n=0$, no special switches were flipped, and the number of lights on is the interval $[0,k]$. None of these intervals overlap, so we can determine $2n$.

From the above observation, we know that the $2n$ groups turned on in virtue of the special switches will have more lights on than the other $m-2n$ groups. So to determine these $2n$ groups, we simply list the groups in decreasing order of number of lights on; the first $2n$ are the groups whose lights were turned on in virtue of the special switches. This will tell us exactly which special switches were flipped, and we can then determine easily which normal switches were flipped. Thus each of the $\sum_{j=0}^k\binom{mk+m-1}{j}$ possible switch positions generates a unique light pattern.

On the other hand, the total number of light patterns possible is $2^{mk}$, so the number of light patterns you can generate is $\leq 2^{mk}$

$\endgroup$
  • $\begingroup$ Maybe it will be easier to distinguish between the different special-switch patterns if you make the following change: each special-switch $i$ (for $i=1,...,m-1$) toggles group $i$ and group $m$. $\endgroup$ – Erel Segal-Halevi Jan 11 '18 at 17:37
  • $\begingroup$ @ErelSegal-Halevi Yes, that does simplify working out the details. I'll make that edit now. Thanks! $\endgroup$ – Y. Forman Jan 11 '18 at 18:22
  • $\begingroup$ @ErelSegal-Halevi Edited. $\endgroup$ – Y. Forman Jan 11 '18 at 18:52
  • $\begingroup$ Beautiful answer. Thanks! BTW why did you remove your previous answer? $\endgroup$ – Erel Segal-Halevi Jan 12 '18 at 2:51
  • $\begingroup$ @ErelSegal-Halevi One step in my "proof" had the inequality going the wrong way... $\endgroup$ – Y. Forman Jan 12 '18 at 2:53
2
$\begingroup$

If $k = 0$, the inequality holds obviously. Now consider a fixed $k \geqslant 1$.

For $m = 1$,$$ \sum_{j = 0}^k \binom{mk + m - 1}{j} = \sum_{j = 0}^k \binom{k}{j} = 2^k = 2^{mk}. $$ For $m = 2$,$$ \sum_{j = 0}^k \binom{mk + m - 1}{j} = \sum_{j = 0}^k \binom{2k + 1}{j} = \frac{1}{2} \cdot 2^{2k + 1} = 2^{mk}. $$ Suppose the inequality holds for $m \ (m \geqslant 2)$. Because for $0 \leqslant j \leqslant k$,\begin{align*} &\mathrel{\phantom{=}} \left. \binom{(m + 1)k + m}{j} \middle/ \binom{mk + m - 1}{j} \right.\\ &= \frac{((m + 1)k + m) \cdots ((m + 1)k + m - j + 1)}{(mk + m - 1) \cdots (mk + m - j)}\\ &= \prod_{l = 1}^j \frac{(m + 1)k + m - l + 1}{mk + m - l} = \prod_{l = 1}^j \left( 1 + \frac{k + 1}{mk + m - l} \right)\\ &\leqslant \left( 1 + \frac{k + 1}{2k + 2 - k} \right)^j = \left( 1 + \frac{k + 1}{k + 2} \right)^j < 2^j \leqslant 2^k, \end{align*} then$$ \sum_{j = 0}^k \binom{(m + 1)k + m}{j} \leqslant 2^k \sum_{j = 0}^k \binom{mk + m - 1}{j} \leqslant 2^k \cdot 2^{mk} = 2^{(m + 1)k}. $$ By induction on $m$, the inequality holds for all $m \in \mathbb{N}_+$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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