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!

  • 2
    $\begingroup$ 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). $\endgroup$ – TerranDrop Jan 13 '16 at 8:22
  • $\begingroup$ Do you mean $\binom{n}{k} \le (ne/k)^k$ instead of $\sum_{i=0}^k \binom{n}{i} \le (ne/k)^k$ ? $\endgroup$ – permanganate Mar 31 '16 at 19:38
  • $\begingroup$ @angryavian where can the proof to the first inequality be found? $\endgroup$ – 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$.

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

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.