# 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:

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