3
$\begingroup$

I have two inequalities that I can't prove:

  1. $\displaystyle{n\choose i+k}\le {n\choose i}{n-i\choose k}$
  2. $\displaystyle{n\choose k} \le \frac{n^n}{k^k(n-k)^{n-k}}$

What is the best way to prove them? Induction (it associates with simple problems, but sometimes I find it difficult to use, what is worrying), or maybe combinatorial interpretation?

3 Answers 3

3

For the first one, if you write out all the binomial coefficients and cancel identical factors on both sides, you're left with

$\frac1{(i+k)!}\le\frac1{i!}\frac1{k!}\;,$

which is clearly true.

For the second one, you can use Stirling's approximation in the form

$\sqrt{2\pi}\ n^{n+1/2}\mathrm e^{-n} \le n! \le \mathrm e\ n^{n+1/2}\mathrm e^{-n}\;,$

which for $k(n-k)\gt0$ yields

$ \begin{align} \binom nk &=\frac{n!}{k!(n-k)!} \\ &\le \frac{\mathrm e\ n^{n+1/2}\mathrm e^{-n}}{\sqrt{2\pi}\ k^{k+1/2}\mathrm e^{-k}\sqrt{2\pi}\ (n-k)^{n-k+1/2}\mathrm e^{-(n-k)}} \\ &= \frac{\mathrm e}{2\pi}\sqrt{\frac{n}{k(n-k)}}\frac{n^n}{k^k(n-k)^{n-k}} \\ &\le \frac{n^n}{k^k(n-k)^{n-k}}\;. \end{align} $

For $k(n-k)=0$, equality holds in your inequality if we interpret $0^0$ as $1$.

2
  1. Let $S_j^n:=\{A\subset [n],|A|=j\}$. Let $S'\subset S_k^{n-i}\times S_i^n$ which consists of pairs of disjoint subsets. The map $\varphi\colon S'\to S_{i+k}^n,\varphi(A,B)=A\cup B$ is onto, hence $|S'|\geq |S_{i+k}^n|=\binom n{i+k}$. Since $S'\subset S_k^{n-i}\times S_i^n$, its cardinal is smaller than the cardinal of the product, which gives the result.

  2. We have to show that $k^k(n-k)^{n-k}\binom nk\leq n^n.$ The LHS is the number of maps from $[n]$ to $[n]$ such that there exists a susbet of $k$ element which is stable and its complement is also stable, and the RHS is the total number of maps from $[n]$ to $[n]$.

  • 0
    But you want $\le$, so counting at least some number of maps doesn't help?2012-08-02
1

The first, after writing down the factorials and some canceling becomes $(i+k)! \geq i!k!$

The second works with induction. Show that the inequality is true with $n = k$ and then show that $\binom{n+1}{k} = \binom{n}{k} * \frac{n+1}{n+1-k} \leq \frac{n^n}{k^k(n-k)^{n-k}} * \frac{n+1}{n+1-k} \leq \frac{(n+1)^{n+1}}{k^k(n+1-k)^{n+1-k}}$

  • 0
    You're right. I need to show that $\frac{n^n}{(n-k)^{n-k}} \leq \frac{(n+1)^n}{(n+1-k)^{n-k}}$ as the $+1$ comes from a factor on both sides. It does seem tricky, I'll think about it.2012-08-02