# 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?

-
$\frac{nCk}{nCk-1}=\frac{n-k+1}{k}$. Or,$nCk>=<nCk-1$ according to:$n-k+1>=<k$,that is n-1>=<2k.The coefficient of middle most term in a binomial expansion of the type: $(1+x)^n$: has the largest value for nCr.There may be two terms producing the largest binomial coefficient. –  Anamitra Palit Dec 4 '11 at 0:50
The post said that $n \le k$, which is most likely a typo; I corrected that. –  Srivatsan Dec 4 '11 at 0:57
Oh, sorry again. And thanks. :) –  mcb Dec 4 '11 at 1:00
If you keep n fixed and increase k from zero to n , then nCk will first increase to a maximum value[this maximum value may get repeated twice] and them decrease.If you keep k fixed and then increase n the value of nCk will go on increasing. –  Anamitra Palit Dec 4 '11 at 1:01

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

-
Sorry, I forgot to add that! –  mcb Dec 4 '11 at 0:47
@mcb It's alright. I removed that note from my answer now that the question is clear. –  Srivatsan Dec 4 '11 at 0:48

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

-

If if you keep $k$ fixed and increase $n$ the value of $\binom{n}{k}$ will increase monotonically.

\begin{align*} \binom{n}{k} &= \frac{n!}{k!(n-k)!} \\ &= \frac{n(n-1)....(n-k+1)}{k!} \tag{1} \end{align*}

If you differentiate the RHS of the above relation wrt to $n$ keeping $k$ constant, you will get a positive [or zero derivative: zero derivative occurs for $k=0$] derivative for $n \geqslant k$ [both $n$ and $k$ positive]. Therefore $\binom{n}{k}$ is a monotonocally increasing function of $n$ when $k$ is kept constant.

You may consider the function expressed by $(1)$ as a continuous function of $n$ [$k$ is of course a fixed integer]. But our interest will be on the integral values of $n$. These values occupy discrete positions on the domain of continuous function considered. For $k=0$, the function is defined to be a constant ($=1$).

-
Dear Anamitra, I cleaned up your post a bit and improved the TeX. Hope that it's ok. I liked your answer and upvoted it. –  Srivatsan Dec 4 '11 at 4:28
Thank you very much.I would try to improve my capabilities with LaTex. –  Anamitra Palit Dec 4 '11 at 5:34