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?
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}$
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}_+$.
