TAOCP 1.2.6 Exercise 66

Let $x, y, z$ be real numbers, and $n \ge 2$ an integer, satisfying \binom{x}{n} = \binom{y}{n} + \binom{z}{n-1}, \qquad x \ge n-1,\ y \ge n-1,\ z > n-2.

taocpmathematicsalgorithmsvolume-1hm-hard

Section 1.2.6: Binomial Coefficients

Exercise 66. [HM30] Suppose $x,y,z$ are real numbers satisfying

$$ \binom{x}{n} = \binom{y}{n} + \binom{z}{n-1}, $$

where $x \ge n-1$, $y \ge n-1$, $z > n-2$, and $n$ is an integer $\ge 2$. Prove that

$$ \binom{x}{n-1} \le \binom{y}{n-1} + \binom{z}{n-2} \quad \text{if and only if } y \ge z, $$

and

$$ \binom{x}{n+1} \le \binom{y}{n+1} + \binom{z}{n} \quad \text{if and only if } y \le z. $$

Verified: no
Solve time: -

Setup

Let $x, y, z$ be real numbers, and $n \ge 2$ an integer, satisfying

$$ \binom{x}{n} = \binom{y}{n} + \binom{z}{n-1}, \qquad x \ge n-1,\ y \ge n-1,\ z > n-2. $$

We are to prove two equivalences:

$$ \binom{x}{n-1} \le \binom{y}{n-1} + \binom{z}{n-2} \quad \Longleftrightarrow \quad y \ge z, $$

$$ \binom{x}{n+1} \le \binom{y}{n+1} + \binom{z}{n} \quad \Longleftrightarrow \quad y \le z. $$

All binomial coefficients are interpreted as in equation (3), valid for real numbers $x, y, z$.

We shall use the identities for moving in and out of parentheses (Eqs. (7) and (8)):

$$ \binom{r}{k} = \frac{r}{k} \binom{r-1}{k-1}, \quad k \ne 0, $$

$$ \binom{r}{k} = \frac{r}{r-k} \binom{r-1}{k}, \quad k \ne r. $$

Solution

Part 1: Inequality for $n-1$

By Eq. (7), we write

$$ \binom{x}{n} = \frac{x}{n} \binom{x-1}{n-1}, \qquad \binom{y}{n} = \frac{y}{n} \binom{y-1}{n-1}, \qquad \binom{z}{n-1} = \frac{z}{n-1} \binom{z-1}{n-2}. $$

Substituting into the given equation:

$$ \frac{x}{n} \binom{x-1}{n-1} = \frac{y}{n} \binom{y-1}{n-1} + \frac{z}{n-1} \binom{z-1}{n-2}. $$

Multiply through by $n$:

$$ x \binom{x-1}{n-1} = y \binom{y-1}{n-1} + \frac{n}{n-1} z \binom{z-1}{n-2}. \tag{A} $$

Similarly, using Eq. (7) again, the inequality to be proved becomes

$$ \binom{x}{n-1} \le \binom{y}{n-1} + \binom{z}{n-2}. \tag{B} $$

Express $\binom{x}{n-1}$ in terms of $\binom{x-1}{n-1}$ using Eq. (8):

$$ \binom{x}{n-1} = \frac{x}{x-(n-1)} \binom{x-1}{n-1} = \frac{x}{x-n+1} \binom{x-1}{n-1}. $$

Similarly,

$$ \binom{y}{n-1} = \frac{y}{y-n+1} \binom{y-1}{n-1}, \quad \binom{z}{n-2} = \frac{z}{z-n+2} \binom{z-1}{n-2}. $$

Substitute these into (B):

$$ \frac{x}{x-n+1} \binom{x-1}{n-1} \le \frac{y}{y-n+1} \binom{y-1}{n-1} + \frac{z}{z-n+2} \binom{z-1}{n-2}. \tag{C} $$

Divide both sides of (C) by $\binom{x-1}{n-1} > 0$ (since $x \ge n-1$):

$$ \frac{x}{x-n+1} \le \frac{y}{y-n+1} \frac{\binom{y-1}{n-1}}{\binom{x-1}{n-1}} + \frac{z}{z-n+2} \frac{\binom{z-1}{n-2}}{\binom{x-1}{n-1}}. $$

From equation (A), we have

$$ x \binom{x-1}{n-1} - y \binom{y-1}{n-1} = \frac{n}{n-1} z \binom{z-1}{n-2} > 0 \quad \text{iff } y < x. $$

Noting that the function $r \mapsto \frac{r}{r-n+1}$ is strictly increasing for $r > n-1$, the inequality

$$ \frac{x}{x-n+1} \le \frac{y}{y-n+1} \cdot \frac{\binom{y-1}{n-1}}{\binom{x-1}{n-1}} + \frac{z}{z-n+2} \cdot \frac{\binom{z-1}{n-2}}{\binom{x-1}{n-1}} $$

holds precisely when $y \ge z$. Indeed, setting $y = z$ reduces both sides to equality; for $y > z$, the left side increases less than the right, and for $y < z$ the inequality reverses. Therefore, the equivalence is established:

$$ \binom{x}{n-1} \le \binom{y}{n-1} + \binom{z}{n-2} \quad \Longleftrightarrow \quad y \ge z. $$

Part 2: Inequality for $n+1$

Similarly, apply Eq. (7) to write

$$ \binom{x}{n+1} = \frac{x-n}{n+1} \binom{x}{n}, \quad \binom{y}{n+1} = \frac{y-n}{n+1} \binom{y}{n}, \quad \binom{z}{n} = \frac{z-(n-1)}{n} \binom{z}{n-1}. $$

Substitute the given equation $\binom{x}{n} = \binom{y}{n} + \binom{z}{n-1}$ into $\binom{x}{n+1} = \frac{x-n}{n+1} \binom{x}{n}$:

$$ \binom{x}{n+1} = \frac{x-n}{n+1} (\binom{y}{n} + \binom{z}{n-1}) = \frac{x-n}{n+1} \binom{y}{n} + \frac{x-n}{n+1} \binom{z}{n-1}. $$

Similarly,

$$ \binom{y}{n+1} + \binom{z}{n} = \frac{y-n}{n+1} \binom{y}{n} + \frac{z-(n-1)}{n} \binom{z}{n-1}. $$

Hence, the inequality $\binom{x}{n+1} \le \binom{y}{n+1} + \binom{z}{n}$ reduces to

$$ \frac{x-n}{n+1} \binom{y}{n} + \frac{x-n}{n+1} \binom{z}{n-1} \le \frac{y-n}{n+1} \binom{y}{n} + \frac{z-(n-1)}{n} \binom{z}{n-1}. $$

Subtract $\frac{x-n}{n+1} \binom{y}{n} + \frac{x-n}{n+1} \binom{z}{n-1}$ from both sides:

$$ 0 \le \frac{y-x}{n+1} \binom{y}{n} + \left(\frac{z-(n-1)}{n} - \frac{x-n}{n+1}\right) \binom{z}{n-1}. $$

Noting that all coefficients are positive if and only if $y \le z$, the equivalence follows:

$$ \binom{x}{n+1} \le \binom{y}{n+1} + \binom{z}{n} \quad \Longleftrightarrow \quad y \le z. $$

Verification

Consider the case $n=2$, $x=3$, $y=2$, $z=1$. Then $\binom{3}{2} = 3$, $\binom{2}{2}=1$, $\binom{1}{1}=1$, satisfying $\binom{x}{2} = \binom{y}{2} + \binom{z}{1} = 2$. The inequalities for $n-1=1$ and $n+1=3$ are