1
$\begingroup$

I need to find an upper bound for

$$\binom{n+\epsilon}{k} \binom{2n-k}{n}$$ where $\epsilon>0$ and $k,n$ are positive integers with $0 \leq k \leq n$.

I think an upper bound should be with $k=n/2$ or something around there, not sure how to prove it.

  • 0
    I've made some edits to your question; apologies if I changed your intended meaning in any way. Just to double-check, $\epsilon$ is also an integer here, right?2012-06-16
  • 0
    Zev: Yes, epsilon is an integer, you could take epsilon to be 2 or 3 if needed.2012-06-16
  • 0
    Just to be clear, $\epsilon$ and $n$ are fixed, and you want to find the value of $k$ that maximizes the expression?2012-06-16

1 Answers 1

2

$$a_k:=\binom{n+\epsilon}{k}*\binom{2n-k}{n} =\frac{(n+\epsilon)!}{k!(n+\epsilon-k)!}\frac{(2n-k)!}{n!(n-k)!} $$

$$\frac{a_{k+1}}{a_k}=\frac{(n+1+\epsilon)!}{k!(n+1+\epsilon-k)!}\frac{(2n+2-k)!}{(n+1)!(n+1-k)!}\frac{k!(n+\epsilon-k)!}{(n+\epsilon)!}\frac{n!(n-k)!}{(2n-k)!} $$

$$\frac{a_{k+1}}{a_k}=\frac{(n+1+\epsilon)}{(n+1+\epsilon-k)}\frac{(2n+2-k)(2n+1-k)}{(n+1)(n+1-k)}$$

Now, solve

$$\frac{a_{k+1}}{a_k} \geq 1$$

This is quadratic in $k$ and gives you the monotony of $a_k$, which yields the max/min.