Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
$\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
add comment

3 Answers

up vote 10 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.