Sequence of Binomial Coefficients is Strictly Increasing to Half Upper Index

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z_{>0}$ be a strictly positive integer.

Let $\dbinom n k$ be the binomial coefficient of $n$ over $k$ for a positive integer $k \in \Z_{\ge 0}$.

Let $S_n = \left\langle{x_k}\right\rangle$ be the sequence defined as:

$x_k = \dbinom n k$


Then $S_n$ is strictly increasing exactly where $0 \le k < \dfrac n 2$.


Corollary 1

Let $n \in \Z_{>0}$ be a strictly positive integer.

Let $\dbinom n k$ be the binomial coefficient of $n$ over $k$ for a positive integer $k \in \Z_{\ge 0}$.

Let $S_n = \left\langle{x_k}\right\rangle$ be the sequence defined as:

$x_k = \dbinom n k$


Then $S_n$ is strictly decreasing exactly where $\dfrac n 2 < k \le n$.


Corollary 2

Maximum Value of Binomial Coefficient

Proof

When $k \ge 0$, we have:

\(\displaystyle \binom n {k + 1}\) \(=\) \(\displaystyle \frac {n!} {\left({k + 1}\right)! \left({n - k - 1}\right)!}\) Definition of Binomial Coefficient
\(\displaystyle \) \(=\) \(\displaystyle \frac {n - k} {n - k} \frac {n!} {\left({k + 1}\right)! \left({n - k - 1}\right)!}\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {n - k} {\left({k + 1}\right) \left({n - k}\right)} \frac {n!} {k! \left({n - k - 1}\right)!}\) extracting $k + 1$ from its factorial
\(\displaystyle \) \(=\) \(\displaystyle \frac {n - k} {k + 1} \frac {n!} {k! \left({n - k}\right)!}\) inserting $n - k$ into its factorial
\(\displaystyle \) \(=\) \(\displaystyle \frac {n - k} {k + 1} \binom n k\) Definition of Binomial Coefficient


In order for $S_n$ to be strictly increasing, it is necessary for $\dfrac {n - k} {k + 1} > 1$.

So:

\(\displaystyle \dfrac {n - k} {k + 1}\) \(>\) \(\displaystyle 1\)
\(\displaystyle \iff \ \ \) \(\displaystyle n - k\) \(>\) \(\displaystyle k + 1\)
\(\displaystyle \iff \ \ \) \(\displaystyle n\) \(>\) \(\displaystyle 2 k + 1\)
\(\displaystyle \iff \ \ \) \(\displaystyle n\) \(>\) \(\displaystyle 2 \left({k + 1}\right) - 1\)

Thus $\dbinom n {k + 1} > \dbinom n k$ if and only if $k + 1$ is less than half of $n$.

Hence the result.

$\blacksquare$