我們愛老師 老師愛我們

This is the title of the colloquium talk by Doron Zeilberger
at Columbia this week. I record his fancy proof here.

Definition. Let $A$ be a set of cardinality $n, C^n_k \equiv$ the number of subsets of cardinality $k.$ Explicitly $C^n_k = \frac{n!}{(n-k)!k!}.$

Theorem. $C^n_k \leq C^n_{k+1}$ for $k< \frac{n}{2}$

Proof:

Plan: We construct an injective linear map $M: V_{1} \rightarrow V_{2}$, where $V_{1}, V_{2}$ are two vector spaces over $\mathds{R}$(any field is fine) with dimensions $C^n_k, C^n_{k+1}$ respectively.

Let $S_{1}, S_{2}$ be the family of subsets of cardinality $k, k+1$ respectively. $V_{i}\equiv \{\sum a_{\alpha}s_{\alpha} \mid a_{j} \in \mathds{R}, s_{\alpha} \in S_{i} \}$
We view subsets as the basis of $V_{i}.$ To define a linear map, we only need to specify its image on the basis and extend linearly. $M(s) = \sum_{j \notin s} s \cup \{ j\}$ (Add one more element.)

Claim: $M$ is injective.
We define a linear map $L: V_{2} \rightarrow V_{1}, L(s) = \sum_{j \in s} s-\{j\}.$(Take away one element) The key fact is: $LM - ML = (n-2k)Id$ (leave to the readers as an exercise.) If $M(f) =0,$ then $M^{i}L^{i}(f) = c(i)f,$ where $c(i) = i(-1)^{i}(n-2k)^{i}$(by induction.) In particular, $c(i) \neq 0.$ But $L^{k}=0$(the empty set) from the definition. So $f=0.$

Appended on 3/13:

Thanks for LLR's careful clarification in his reply. His setting is right. $L, M$ must come with an index to indicate its domain. Let's derive the right formula for $c(i)$. I use different convention from LLR's. Let $L(k):V(k) \rightarrow V(k-1)$ to remind ourselves the domain of $L(k)$ better. So we have $L(k+1)M(k) - M(k-1)L(k) = (n -2k)$(I omit the identity operator henceforth.) $c(1) = n - 2k, c(2) = (n - 2k)[(n - 2k)(n - 2(k-1))].$

\begin{align*}

M(k-1)M(k-2)M(k-3)L(k-2)L(k-1)L(k) \\

&= M(k-1)M(k-2)[L(k-1)M(k-2) - (n - 2(k-2))]L(k-1)L(k) \\

&= M(k-1)M(k-2)L(k-1)M(k-2)L(k-1)L(k) - (n - 2(k-2)) c(2) \\

&= M(k-1)M(k-2)L(k-1)[L(k)M(k-1) - (n - 2(k-1))]L(k) - (n - 2(k-2))c(2) \\

&= c(2) M(k-1)L(k) - (n - 2(k-1))c(2) - (n - 2(k-2))c(2) \\

&= -c(2)[(n-2k) + (n - 2(k-1)) + (n - 2(k-2))]

\end{align*}

So the recurrent relation is $c(i) = (-1)^i c(i-1)[(n-2k) + \cdots + (n - 2(k-i+1))] $

$L, M$ makes sense up to $L(1), M(0) \ \ (V(0) = \{\mathds{R}\})$. The formula holds up to i= k.

The above approach is an unnecessary example of "algebraicalization" used in combinatorics. It's indeed hard for we analysts to believe such axiomatic approach works. But this seems to be of current interests. Another hot topic is the categorification in representation theory and low dimensional topology, which is fruitful in recent years.