# How to prove if function is increasing

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?

-
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

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.

-

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

-

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.

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

-
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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9559157490730286, "perplexity": 316.97123605243866}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-06/segments/1422115869264.47/warc/CC-MAIN-20150124161109-00103-ip-10-180-212-252.ec2.internal.warc.gz"}