X Choose n leq y Choose n + z Choose n-1 where n leq y leq x leq y+1 and n-1 leq z leq y
Theorem
Let $n \in \Z_{\ge 0}$ be a positive integer.
Let $x, y \in \R$ be real numbers which satisfy:
- $n \le y \le x \le y + 1$
Let $z$ be the unique real number $z$ such that:
- $\dbinom x {n + 1} = \dbinom y {n + 1} + \dbinom z n$
where $n - 1 \le z \le y$.
Its uniqueness is proved at Uniqueness of Real $z$ such that $\dbinom x {n + 1} = \dbinom y {n + 1} + \dbinom z n$.
Then:
- $\dbinom x n \le \dbinom y n + \dbinom z {n - 1}$
Proof
If $z \ge n$, then from Ordering of Binomial Coefficients:
- $\dbinom z {n + 1} \le \dbinom y {n + 1}$
Otherwise $n - 1 \le z \le n$, and:
- $\dbinom z {n + 1} \le 0 \le \dbinom y {n + 1}$
In either case:
- $(1): \quad \dbinom z {n + 1} \le \dbinom y {n + 1}$
Therefore:
\(\ds \dbinom {z + 1} {n + 1}\) | \(=\) | \(\ds \dbinom z {n + 1} + \dbinom z n\) | Pascal's Rule | |||||||||||
\(\ds \) | \(\le\) | \(\ds \dbinom y {n + 1} + \dbinom z n\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dbinom x {n + 1}\) | by hypothesis |
and so $x \ge z + 1$.
Now we are to show that every term of the summation:
- $\ds \binom x {n + 1} - \binom y {n + 1} = \sum_{k \mathop \ge 0} \dbinom {z - k} {n - k} t_k$
where:
- $t_k = \dbinom {x - z - 1 + k} {k + 1} - \dbinom {y - z - 1 + k} {k + 1}$
is negative.
Because $z \ge n - 1$, the binomial coefficient $\dbinom {z - k} {n - k}$ is non-negative.
Because $x \ge z + 1$, the binomial coefficient $\dbinom {x - z - 1 + k} {k + 1}$ is also non-negative.
Therefore:
- $z \le y \le x$
implies that:
- $\dbinom {y - z - 1 + k} {k + 1} \le \dbinom {x - z - 1 + k} {k + 1}$
When $x = y$ and $z = n - 1$ the result becomes:
- $\dbinom x n \le \dbinom x n + \dbinom {n - 1} {n - 1}$
which reduces to:
- $\dbinom x n \le \dbinom x n + 1$
which is true.
Otherwise:
\(\ds \dbinom x n - \dbinom y n - \dbinom z {n - 1}\) | \(=\) | \(\ds \sum_{k \mathop \ge 0} \dbinom {z - k} {n - 1 - k} \left({t_k - \delta_{k 0} }\right)\) | where $\delta_{k 0}$ is the Kronecker delta | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \ge 0} \dfrac {n - k} {z - n + 1} \dbinom {z - k} {n - k} \left({t_k - \delta_{k 0} }\right)\) | Factors of Binomial Coefficient |
This is less than or equal to:
\(\ds \sum_{k \mathop \ge 0} \dfrac {n - 1} {z - n + 1} \dbinom {z - k} {n - k} \left({t_k - \delta_{k 0} }\right)\) | \(=\) | \(\ds \dfrac {n - 1} {z - n + 1} \left({\dbinom x {n + 1} - \dbinom y {n + 1} - \dbinom z n}\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 0\) | because $t_0 - 1 = x - y - 1 \le 0$ |
Hence the result.
$\blacksquare$
Sources
- 1979: László Lovász: Combinatorial Problems and Exercises: Problem $13.31 \ \text {(a)}$
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Exercise $66$