2
$\begingroup$

Prove that the binomial coefficient $\binom {n}{k} = \frac {n!} {(n-k)!k!}$, viewed as a function of $k$, has maximum at $k=\lfloor n/2 \rfloor, \lceil n/2 \rceil$ if $n$ is odd and maximum at $k=n/2$ if $n$ is even.

Also how do I see that $\binom {n}{k} = \frac {n!} {(n-k)!k!}$ is increasing on $[0;n/2]$ and decreasing on $[n/2;n]$ ?

I see that $\binom {n}{k} = \frac {n!} {(n-k)!k!} = \frac {n!} {(n-(n-k))!(n-k)!} = \binom {n}{n-k}$, so clearly the function is symmetric around $n/2$.

If it is possible, I would like an answer not depending on the derivative, but more on algebra.

$\endgroup$

marked as duplicate by Steven Stadnicki, user147263, muaddib, Strants, Rory Daulton Jul 18 '15 at 21:38

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4
$\begingroup$

HINT:

Keeping integer $n(>0)$ constant,

$$\frac{\binom nk}{\binom n{k-1}}=\frac{n-k+1}k$$

Now this ratio will be $\displaystyle<=>1$ according as $\displaystyle\frac{n-k+1}k<=>1$

So, $\displaystyle\binom nk>\binom n{k-1}\iff \frac{n-k+1}k>1\iff k\le\frac{n+1}2$

$\endgroup$
  • $\begingroup$ Thank you, I really like your answer, because it explains the question not only in words but also in numbers. Will the "tradional" way of proving the argument be to look at the derivative ? $\endgroup$ – Shuzheng Jun 7 '14 at 9:57
  • $\begingroup$ @user111854, My Pleasure. Please explain your last statement $\endgroup$ – lab bhattacharjee Jun 7 '14 at 11:36
  • $\begingroup$ I mean, would the intuitive and most easy way of proving the statement be to look at the derivative and find a point where the slope is $0$ ? I guess we would have slope $= 0$ at $n/2$ ? $\endgroup$ – Shuzheng Jun 8 '14 at 7:31
4
$\begingroup$

Since you realize that $\binom{n}{k} = \binom{n}{n-k}$, then we just need to prove that the function is increasing from $k=0$ to $\frac{n}{2}$ or decreasing in the other half. Also, $\binom{n}{k}$ is number of ways of choosing(rejecting) $k$ objects from $n$ objects, or of rejecting(choosing) $n-k$ objects. This is increasing. You can choose 1 object in $n$ ways, then for two objects, the first in $n$ ways and second in $(n-1)$ ways, but since order doesn't matter we get $\frac{n(n-1)}{2}$ ways. Not third object can be chosen in $n-3$ ways and again ignoring order we get $f(n,2)*\frac{(n-2)}{3}$ ways etc. As is clear we are multiplying the previous number by a factor greater than 1, so from 0 upwards it is increasing. But once we reach $\frac{n}{2}$, we see that choosing $\frac{n}{2}+k, (0\le k\le \frac{n}{2})$ objects is same as rejecting $\frac{n}{2}-k$ objects, so since till this point the function was increasing, and from here the values are being reflected, we can conclude that the function is decreasing beyond this point.

$\endgroup$

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