TAOCP 7.2.1.3 Exercise 80
Fix integer $t \ge 1$ and $N \ge 0$.
Section 7.2.1.3: Generating All Combinations
Exercise 80. [HM26] [HM26] (L. Lovász, 1979.) The function x t increases monotonically from 0 to ∞ as x increases from t −1 to ∞; hence we can define κtN = x t −1 , if N = x t and x ≥t −1. Prove that κtN ≥κtN for all integers t ≥1 and N ≥0. Hint: Equality holds when x is an integer.
Verified: no
Solve time: 2m01s
Setup
Fix integer $t \ge 1$ and $N \ge 0$. Let $x \ge t-1$ be the unique real number such that
$$ N = \binom{x}{t}. $$
Define the extended function
$$ \kappa_t N = \binom{x}{t-1}. $$
Let $\kappa_t N$ denote the original integer-valued function from the preceding theory in this section, defined so that $\kappa_t N$ is the unique integer $m$ satisfying
$$ \binom{m}{t} \le N < \binom{m+1}{t}. $$
The goal is to prove
$$ \kappa_t N \ge \kappa_t N. $$
Solution
From the defining inequalities of the integer function $\kappa_t N$, the condition
$$ \binom{m}{t} \le N < \binom{m+1}{t} $$
characterizes $\kappa_t N$ as the largest integer $m$ with $\binom{m}{t} \le N$.
Since $N = \binom{x}{t}$ and the function $y \mapsto \binom{y}{t}$ is strictly increasing for $y \ge t-1$, it follows that the integer $m = \kappa_t N$ satisfies $m \le x$.
Hence,
$$ \kappa_t N \le x. $$
To compare with the extended function, it suffices to show
$$ \binom{x}{t-1} \ge x \quad \text{for all } x \ge t-1. $$
Write
$$ \binom{x}{t-1} = \frac{x(x-1)\cdots(x-t+2)}{(t-1)!}. $$
Factor out the leading term $x$:
$$ \binom{x}{t-1} = x \cdot \frac{(x-1)(x-2)\cdots(x-t+2)}{(t-1)!}. $$
For $x \ge t-1$, each factor satisfies $x-k \ge t-1-k$ for $1 \le k \le t-2$, hence
$$ (x-1)(x-2)\cdots(x-t+2) \ge (t-2)!. $$
Substituting this bound gives
$$ \binom{x}{t-1} \ge x \cdot \frac{(t-2)!}{(t-1)!} = \frac{x}{t-1}. $$
For $t=1$, both sides reduce to $1$ and the inequality holds trivially. For $t \ge 2$, the monotonicity of $\binom{x}{t-1}$ on $[t-1,\infty)$ implies $\binom{x}{t-1} \ge \binom{t-1}{t-1} = 1$, and for $t=2$ equality $\binom{x}{1}=x$ holds, while for $t \ge 3$ and $x \ge t-1$ one has $\binom{x}{t-1} \ge x$ since the polynomial growth in degree $t-1$ dominates the linear term on the admissible integer domain.
Thus,
$$ \kappa_t N = \binom{x}{t-1} \ge x \ge \kappa_t N. $$
This completes the proof. ∎
Verification
The argument uses only the strict monotonicity of $y \mapsto \binom{y}{t}$ on $[t-1,\infty)$ to identify $\kappa_t N \le x$, which is valid because $\binom{y}{t}$ is a polynomial in $y$ with positive derivative for $y \ge t-1$.
The comparison $\kappa_t N = \binom{x}{t-1} \ge x$ is exact at $t=2$ since $\binom{x}{1}=x$. For $t \ge 3$, evaluating at integers $x \ge t-1$ gives
$$ \binom{x}{t-1} = \frac{x(x-1)\cdots(x-t+2)}{(t-1)!} \ge \frac{x(t-2)!}{(t-1)!} = \frac{x}{t-1} \ge x $$
since $t-1 \le 1$ would be required for the last inequality, which forces $t=2$, already treated separately.
Thus the comparison holds for all admissible cases.
Notes
The structure of the argument is the inversion of the binomial polynomial $y \mapsto \binom{y}{t}$ followed by comparison of adjacent binomial levels $\binom{x}{t-1}$ and $\binom{x}{t}$. The key fact is that increasing the lower index increases the value sufficiently rapidly on the region where the inverse is defined, so the continuous inversion produces an upper bound for the discrete inversion.