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
    On second thought, you're overcounting on the left-hand side, since a map that leaves several $k$-element subsets stable is counted several times; e.g. the identity is counted $\binom nk$ times.2012-08-02
  • 0
    I agree, at least it counts the number of maps which leave a unique set of $k$ elements stable and its complement.2012-08-02
  • 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
    How does that last step work? One of the factors in the denominator has increased.2012-08-02
  • 0
    That works since $x^x$ grows faster for larger values of $x$.2012-08-02
  • 0
    I guess it probably works, but it's a bit handwaving so far, since you also have the factor $(n+1)/(n+1-k)$.2012-08-02
  • 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