3
$\begingroup$

I am would like to prove ${n \choose k} \le {n \choose k-1} +{n \choose k+1}$.

I can use the monotonicity property of the binomial coefficient to show this.

However, I wonder if there is an easy way to see this "immediately".

(Perhaps a combinatorial proof?)

Any suggestions are welcome.

$\endgroup$
  • 1
    $\begingroup$ Algebraically, using twice the defining identity $${i\choose j}={i-1\choose j-1}+{i-1\choose j}$$ and the fact that every binomial coefficient is nonnegative, one gets $${n\choose k}={n-1\choose k-1}+{n-1\choose k}\leqslant\left({n-1\choose k-2}+{n-1\choose k-1}\right)+\left({n-1\choose k}+{n-1\choose k+1}\right)={n\choose k-1}+{n\choose k+1}$$ which provides also an explicit formula for the excess $${n\choose k-1}+{n\choose k+1}-{n\choose k}$$ $\endgroup$ – Did Jul 7 '17 at 16:58
7
$\begingroup$

Given a $k$-subset $S \subset \{1,\ldots, n\}$, define $f(S)$ as follows: if $1 \in S$, let $f(S) = S - \{1\}$, otherwise, let $f(S) = S \cup \{1\}$. Observe that $f$ is an injection and always $|f(S)| \in \{k-1, k+1\}$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

This is based on Did's comment:

By an easy (and very well-known) combinatorial argument, we have $$ {n\choose k}={n-1\choose k}+{n-1\choose k-1}.$$

The following two inequalities are also immediate due to combinatorial reasons:

$${n-1\choose k} \le {n\choose k+1}.$$

(To any choice of $k$ out of $n-1$, append the extra ball).

$${n-1\choose k-1} \le {n\choose k-1}.$$

(Just don't choose the last ball).

Putting these two together, we get $$ {n\choose k} \le {n\choose k+1}+{n\choose k-1}$$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Directly: $$C_k^n\le C_{k-1}^n+C_{k+1}^n=\underbrace{C_{k-2}^{n-1}}_{0 \ if \ k-2<0}+\underbrace{C_{k-1}^{n-1} +C_{k}^{n-1}}_{C_k^n}+\underbrace{C_{k+1}^{n-1}}_{0 \ if \ k+1>n}.$$

| cite | improve this answer | |
$\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.