Prove that $\sum_{i=0}^{m}{\binom{n-i}{k}}=\binom{n+1}{k+1}-\binom{n-m}{k+1}$

Question

Question

I need to prove the following expression for $n>m+k$:

$$ \sum_{i=0}^{m}{\binom{n-i}{k}}=\binom{n+1}{k+1}-\binom{n-m}{k+1} $$

My Solution

Define $S$ as a set containing the first $n+1$ positive integers. From $S$ we create subsets with $k+1$ elements.

Since $\binom{n-i}{k}$ is the number of subsets with $n-i+1$ as their greatest element, the left hand side of the equation gives the number of subsets where the greatest element is greater than $n-m$.

The right hand side is an alternative method to count such subsets; we count the number of all possible subsets then subtract the number of subsets with all elements less than or equal to $n-m$

Because both left hand side and right hand side count the same objects, they must be equal.

I want to know if my solution is correct and if there’s any alternative

Answer 1

Your way is fine.

Here's another way: proceed using induction.

The proposition is true if $m=0$:

$${\binom{n-0}{k}}=\binom{n+1}{k+1}-\binom{n-0}{k+1}$$ because

$${\binom{n}{k}}+\binom{n}{k+1}=\binom{n+1}{k+1}.$$

Suppose it is true that

$$\sum_{i=0}^{m-1}{\binom{n-i}{k}}=\binom{n+1}{k+1}-\binom{n-(m-1)}{k+1}.$$

Then,

$$\sum_{i=0}^{m}{\binom{n-i}{k}}=\sum_{i=0}^{m-1}{\binom{n-i}{k}}+{\binom{n-m}{k}}$$

which equals

$$\binom{n+1}{k+1}-\binom{n-m+1}{k+1}+{\binom{n-m}{k}}$$

which, because

$$\binom{n-m+1}{k+1}=\binom{n-m}{k+1}+\binom{n-m}{k},$$

equals

$$\binom{n+1}{k+1}-\binom{n-m}{k+1}-\binom{n-m}{k}+{\binom{n-m}{k}}=\binom{n+1}{k+1}-\binom{n-m}{k+1}$$

as required.

Answer 2

$$S=\sum_{i=0}^m {n-i \choose k}=\text{Coefficient of $x^k$ in}\sum_{i=0}^m (1+x)^{n-i}$$ $$\implies S=\text{Coefficient of $x^k$ in}~~(1+x)^n\frac{(1+x)^{-m-1}-1}{(1+x)^{-1}-1.}$$ $$\implies S=\text{Coefficient of $x^{k+1}$ in}~~[(1+x)^{n+1}-(1+x)^{n-m}]$$ $$\implies S={n+1 \choose k+1}-{n-m \choose k+1}$$