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

From ProofWiki
Jump to navigation Jump to search

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:

\(\displaystyle \dbinom {z + 1} {n + 1}\) \(=\) \(\displaystyle \dbinom z {n + 1} + \dbinom z n\) Pascal's Rule
\(\displaystyle \) \(\le\) \(\displaystyle \dbinom y {n + 1} + \dbinom z n\)
\(\displaystyle \) \(=\) \(\displaystyle \dbinom x {n + 1}\) by hypothesis

and so $x \ge z + 1$.


Now we are to show that every term of the summation:

$\displaystyle \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:

\(\displaystyle \dbinom x n - \dbinom y n - \dbinom z {n - 1}\) \(=\) \(\displaystyle \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
\(\displaystyle \) \(=\) \(\displaystyle \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:

\(\displaystyle \sum_{k \mathop \ge 0} \dfrac {n - 1} {z - n + 1} \dbinom {z - k} {n - k} \left({t_k - \delta_{k 0} }\right)\) \(=\) \(\displaystyle \dfrac {n - 1} {z - n + 1} \left({\dbinom x {n + 1} - \dbinom y {n + 1} - \dbinom z n}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle 0\) because $t_0 - 1 = x - y - 1 \le 0$

Hence the result.

$\blacksquare$


Sources