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.

Need to prove that function $$P(n,k)=\binom{n}{k}= \frac{n!}{k!(n-k)!}$$ is increasing when $\displaystyle k\leq\frac{n}{2}$.

Is this inductive maths topic?

share|improve this question
1  
Do you mean, fix $n$ and let $k$ increase? Or, do you mean fix $k$ and let $n$ increase? There are two variables. Which one are you wondering about? –  Graphth Sep 15 '12 at 13:26

4 Answers 4

Write out the quotient $\dfrac{P(n,k+1)}{P(n,k)}$. You get $\dfrac{n-k}{k+1}$. Now the conclusion is obvious.

Induction is not necessary.

share|improve this answer

You’re trying to compare $$\frac{n!}{k!(n-k)!}$$ and $$\frac{n!}{(k+1)!(n-k-1)!}\;.$$ Specifically, you’re trying to show that if $k\le n/2$, then

$$\frac{n!}{k!(n-k)!}<\frac{n!}{(k+1)!(n-k-1)!}\;.\tag{1}$$

Actually, this isn’t quite true: if $n=3$ and $k=1$, the two sides of $(1)$ are equal. $(1)$ is true, however, when $k<\frac12(n-1)$; when $k=\frac12(n-1)$, the two sides of $(1)$ are equal.

One way to approach this is to show that the difference

$$\frac{n!}{(k+1)!(n-k-1)!}-\frac{n!}{k!(n-k)!}$$

is positive when $k<\frac12(n-1)$ and $0$ when $k=\frac12(n-1)$. This isn’t difficult if you combine the fractions over a common denominator. Remember that $(n-k)!=(n-k)(n-k-1)!$ and $(k+1)!=(k+1)k!$, and you should have little trouble. (Induction is not needed: it’s just algebra.)

share|improve this answer

Actually you can proceed by induction.

Hint Think about the Pascal's triangle: the base cases $n=1$ or $n=2$ are essentially self-evident. Suppose then the thesis to be true for $n$ and say you want it to prove for $n+1$. Then you may want to use the relation $$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$$ to carry out induction. Hope this helps.

share|improve this answer
    
For the record: my answer does not claim that it is impossible to prove this by induction. I only claim that it is not necessary. –  Rasmus Sep 15 '12 at 10:11
    
@Rasmus I didn't mean that with my first sentence. Just wanted to show an approach by induction. Yours is obviously fine –  uforoboa Sep 15 '12 at 10:13

As $n$ increases, $n!$ increases. As $n$ increases $(n-k)!$ increases. $(n+1)!$ is $(n+1)$ times larger than n!. $(n+1-k)!$ is however only $(n+1-k)$ times greater than $(n-k)!$. Therefore the numerator increases more than the denominator as n increases. Therefore P increases as n increases.

As $k$ increases, $k!$ increases. As $k$ increases $(n-k)!$ decreases. The question is then, what changes at a greater rate: $k!$ or $(n-k)!$. Define the functions $A(x) = x!$ and $B(x) = (n-x)!$. The denominator of $P(n,k)$ is thus $A(k)*B(k)$.

Now $A(k) = k!$ and $B(k) = (n-k)!$.

Also, $A(k+1) = (k+1)! = (k+1)*k!$
Also, $B(k+1) = (n - k - 1)! = (n-k)!/(n-k)$.

Therefore $A(k+1)B(k+1) = (k+1)k!(n-k)!/(n-k) = A(k)B(k)(k+1)/(n-k)$

So $(k+1)/(n-k) \leq 1$ then the function is increasing.

This must be the case since $k \leq n/2$

Therefore P is an increasing function of $k$ and $n$.

share|improve this answer
    
I don't follow your first line. –  Rasmus Sep 15 '12 at 10:14
    
@Chris Usage of Latex is intended to make what you write clearer. Please don't intentionally avoid it. Cheers. –  uforoboa Sep 15 '12 at 10:17
    
It does not follow from the fact that both numerator and denominator are increasing that the fraction is increasing. The fractions $\frac n {n^2}, \frac n {n}, \frac {n^2} {n}$ are respectively decreasing, constant and increasing with increasing $n$. You need to say more to justify your first sentence (which is, in any event, not always true). –  Mark Bennet Sep 15 '12 at 11:49
    
Yes you're correct Mark. I will fix up now. –  Mew Sep 15 '12 at 12:04

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.