# Is ${n \choose k} \le {n \choose k-1} +{n \choose k+1}$ obvious?

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.

• 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}$$ – Did Jul 7 '17 at 16:58

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

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

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