Upper bound for partial sum of binomial coefficients

I am familiar with the proof of the upper bound $\sum_{i=0}^k \binom{n}{i} \le (ne/k)^k$, but I was told that the worse bound $$\sum_{i=0}^k \binom{n}{i} \le (n+1)^k$$ has a simple combinatorial proof, but I cannot see it. I know the left-hand side is the number of ways to select $\le k$ objects from $n$ objects, but I am having trouble with the right-hand side. Any hints or insights would be helpful!

• You can add a "void" item to your collection of $n$ items, and consider you draw $k$ items from this augmented collection (with possible repetition and taking ordering into account). – TerranDrop Jan 13 '16 at 8:22
• Do you mean $\binom{n}{k} \le (ne/k)^k$ instead of $\sum_{i=0}^k \binom{n}{i} \le (ne/k)^k$ ? – permanganate Mar 31 '16 at 19:38
• @angryavian where can the proof to the first inequality be found? – Erel Segal-Halevi Sep 18 '18 at 6:00

Define $E:=\{1,...,n\}$ to be a set of cardinal $n$ :

$$X:=\{A\subseteq E\mid |A|\leq k\}$$

$$Y:=\{f:\{1,...k\}\rightarrow E\cup\{0\}\}$$

Now :

$$\psi : X\rightarrow Y$$

$$A:=\{a_1<...<a_l\}\mapsto f_A$$

Remarking that $|X|\leq |Y|$ is exactly the inequality you want, you just have to find a way to define $f_A$ so that the function $\psi$ is one-to-one.

Hint : Use the fact that any $A\in X$ can be written as $A=\{a_1<...<a_l\}$ with $0\leq l\leq k$.

• Alternatively, $Y:= (E \cup \{0\})^k$. Then mapping $A$ to $(a_1,\ldots, a_l, 0,\ldots,0)$ gives the desired injection? – angryavian Jan 13 '16 at 8:26
• @angryavian, Yep, that is what I had in mind... – Clément Guérin Jan 13 '16 at 8:32