Q:

How can I prove that the binomial coefficient ${n \choose k}$ is monotonically nondecreasing for $n \ge k$? 

I want to prove that the binomial coefficient ${n \choose k}$ for $n \ge k$ is a monotonically nondecreasing sequence for a fixed $k$. How do I do this? 

A:

From the recursive formula for binomial coefficient
$$
\binom{n}{k} = \binom {n-1}{k} + \binom{n-1}{k-1} \qquad (n, k > 0), 
$$
it is clear that $\binom{n}{k} \geqslant \binom{n-1}{k}$.

The claim is even more obvious when one thinks of the combinatorial interpretation of the binomial coefficient.  Every $k$-subset of $\{ 1, 2, \ldots,  n-1 \}$ is also a $k$-subset of $\{1, 2, \ldots, n\}$; so it immediately follows that $\binom{n-1}{k} \leqslant \binom{n}{k}$.

A:

Fix $k \geq 0$.  Show that $${n+1 \choose k} = \frac{(n+1)!}{k!(n+1-k)!}  \geq \frac{n!}{k!(n-k)!}  = {n \choose k}.$$
But this follows whenever $n+1 \geq n+1 - k$, so...

