1
$\begingroup$

I am quite certain that $2\binom{d}{k} \le \binom{2d}{k}$ holds for every positive integers $k,d$, where $1 \le k \le d$.

Is there a simple proof? A combinatorial proof ?

An immediate combinatorial argument gives $2\binom{d}{k} \le \binom{2d}{2k}$, as the LHS corresponds to choosing $k$ elements out of $d$, and then choosing additional $k$ elements out of a distinct new set of $d$ elements. The RHS correspond to an "unconstrained" choice of $2k$ out of $2d$.

(I checked the cases $k=1,d$, and various other examples with "small numbers". For "large" $d$ the asymptotics of the binomial coefficients seems compatible with this inequality).

$\endgroup$
  • 4
    $\begingroup$ When choosing $k$ out of $2d$ elements, you can choose $k$ among the first $d$ or $k$ among the last $d$ (or some mix). This gives $2\binom{d}{k}$ as a lower bound. $\endgroup$ – Wojowu Feb 4 at 11:11
1
$\begingroup$

A "combinatorial proof":

When chosing $k \ge 1$ elements from a $2d$ set ($k \le d$), we can chose $j$ ($0 \le j \le k$) elements from the first $d$ elements and $k-j$ from the last $d$ elements. The number of possibilities is therefore

$$ \binom{2d}{k} = \sum_{j=0}^k \binom{d}{j} \binom{d}{k-j} = 2\binom{d}{k} + \sum_{j=1}^{k-1} \binom{d}{j} \binom{d}{k-j} $$

The "remaining" sum might be empty (if $k=1$) but is clearly not negative.

$\endgroup$
1
$\begingroup$

Since this turned out to be quite trivial, I will just make Wojowu's comment into an answer:

When choosing $k$ out of $2d$ elements, we can choose $k$ among the first $d$ or $k$ among the last $d$ (or some mix). This gives $2\binom{d}{k}$ as a lower bound.

$\endgroup$

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.