A 'non-numerical\analytic' proof that $\binom{n}{k}$ > $\binom{n}{k-1}$ for large $n \in \mathbb{N}$

Question

The number of $k$-subsets of $[n]$ is given by the formula $\binom{n}{k}$ or $^nC_k$. They famously occur in the expansion of $(1+x)^n$ and they are given by the formula $$\binom{n}{k}=\frac{n!}{(n-k)!k!}$$

Using this formula, it is easy to prove the inequality that $\binom{n}{k}>\binom{n}{k-1}$ for large enough $n \in \mathbb{N}$. What this inequality says is that the number of ways of choosing $k-1$-subsets is eventually smaller than the number of ways of choosing $k$-subsets of $[n]$.

One more way of showing this is by observing that $\binom{n}{k}$ is a polynomial in $n$ of degree $k$ and then, we can see that it will outgrow $\binom{n}{k-1}$ which is a lower degree polynomial in $n$.

Is there a more natural way of seeing this inequality without the use of calculations with the use of something more combinatorial-like? Possibly by exhibiting an injection between the $k-1$-subsets and $k$-subsets? Or by another interpretation of the numbers where it is easier to get such an injection? Or something else altogether?

$\mathbf{Remark}$: My supervisor mentioned almost immediately that there was a way to see this using Symmetric Chain Decomposition. But I do not have the luxury of spending that much time on this. I apologise. I would be thankful if you could provide a proof based on the same.

$\mathbf{Tl;dr}: $ What I am looking for is something more along the lines of bijections or a different interpretation of the binomial coefficients that makes the inequality easier to see. I hope the approach doesn't rely heavily on calculations and at the same time, explains why the the inequality reverses for small $n$.

Thank you, in advance.

Answer 1

If you assume $n > 2k - 1$ (and hence $n-k+1 > k$), I think you can use a double counting argument. Consider the following sets :

$$\mathcal{A} = \{(x, A) \in [n] \times \mathcal{P}([n]), |A| = k, \, x \in A\}$$ and $$\mathcal{B} = \{(x, B) \in [n] \times \mathcal{P}([n]), |B| = k-1, \, x \notin B\}$$ We have $|\mathcal{A}| = k \times \binom{n}{k} $ and $|\mathcal{B}| = (n-k+1) \times \binom{n}{k-1}$

But the function $f : \mathcal{A} \to \mathcal{B}$ defined by $f(x,E) = (x, E \setminus \{x\})$ is a bijection (the reciprocal is given by $f^{-1}(x,F) = (x, F \cup \{x\})$). So

$$k \times \binom{n}{k} = (n-k+1) \times \binom{n}{k-1} > k \times \binom{n}{k-1}$$

Which gives you the desired inequality.

Note : another way to look at it is that we're double counting the set $$\mathcal{C} = \{(A,B) \in \mathcal{P}_k([n]) \times \mathcal{P}_{k-1}([n]), \ B \subset A\}$$ either line by line or column by column.

Answer 2

Double counting is possibly the easiest combinatorial proof, however you can make the "naïve injection" idea work if you're willing to move from finite sets to finite dimensional vector spaces.

Let $V$ be the vector space with basis $\{ e_S : S \subseteq [n] \}$. This vector space is graded: $V_i = \operatorname{span}\{e_S : |S| = i\}$.

Now define $\mathsf{X} : V_i \to V_{i + 1}$ by $$\mathsf{X}e_{S} = \sum_{a \notin S} e_{S \cup \{a\}}$$

And similarly, define $\mathsf{Y} : V_{i + 1} \to V_i$ by $$\mathsf{Y}e_{S} = \sum_{a \in S} e_{S \setminus \{a\}}.$$

Now you can check things like $\mathsf{XY} - \mathsf{YX} = 2i - n$. And well, it's a bit too long for me to include here, but $\mathsf{X}, \mathsf{Y}, \mathsf{H} = \mathsf{XY} - \mathsf{YX}$ form a representation of $\mathfrak{sl}_2(\mathbf{C})$ and the general structure theory of $\mathfrak{sl}_2(\mathbf{C})$-representations is that $\dim V_0 \le \dim V_1 \le \dots \le \dim V_{n/2} \ge \dots \ge \dim V_n$.

Reference: http://www.math.uwaterloo.ca/~dgwagner/SL2C.pdf

Answer 3

There is a fairly simple probabilistic argument: as the sum of $n$ independent and uniform (hence symmetric) distributions over $\{0,1\}$, the binomial distribution is symmetric and unimodal. This implies that $\binom{n}{k}$ is increasing over $\left[0,\left\lfloor\frac{n}{2}\right\rfloor\right]$ and $\binom{n}{k}>\binom{n}{k-1}$ holds for sure for any $n > 2k$.

As an alternative, assume $k< n/2$. Then

$$ \frac{1}{\binom{n}{k}}=\frac{k!(n-k)!}{n!}=(n+1)\frac{\Gamma(k+1)\Gamma(n-k+1)}{\Gamma(n+2)}=(n+1)\int_{0}^{1}x^k (1-x)^{n-k}\,dx $$

leads to $$ \binom{n}{k}^{-1} = (n+1)\int_{0}^{1}(x(1-x))^{n/2}\left(\frac{1-x}{x}\right)^{n/2-k}\,dx. $$

Since $\frac{1-x}{x}>1$ on $(0,1)$, the RHS is an increasing (and log-convex) function of $\frac{n}{2}-k$.

Yet another way: by Newton's inequalities, if a polynomial only has negative real zeroes its coefficients form a log-concave sequence. Since $(1+x)^n$ has a unique root (with multiplicity $n$) at $x=-1$, the sequence given by $\binom{n}{k}$ for $k=0,1,\ldots,n-1,n$ is log-concave. It is a symmetric sequence, hence it is increasing over $\left[0,\left\lfloor\frac{n}{2}\right\rfloor\right]$.