Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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}} \\ &= \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$.

share|improve this answer
  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]$.

share|improve this answer
    
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. –  joriki Aug 2 '12 at 9:43
    
I agree, at least it counts the number of maps which leave a unique set of $k$ elements stable and its complement. –  Davide Giraudo Aug 2 '12 at 10:31
    
But you want $\le$, so counting at least some number of maps doesn't help? –  joriki Aug 2 '12 at 10:54

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}}$$

share|improve this answer
    
How does that last step work? One of the factors in the denominator has increased. –  joriki Aug 2 '12 at 9:48
    
That works since $x^x$ grows faster for larger values of $x$. –  Karolis Juodelė Aug 2 '12 at 11:36
    
I guess it probably works, but it's a bit handwaving so far, since you also have the factor $(n+1)/(n+1-k)$. –  joriki Aug 2 '12 at 11:44
    
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. –  Karolis Juodelė Aug 2 '12 at 13:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.