Proving the identity $\sum_{k=0}^{m} \binom{n-k}{m-k}= \binom{n+1}{m}$ .

Question

Today we started talking about generating functions in class. I came across this identity:

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

Here is my proof for this identity (If it is wrong please tell me):

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

I understood that it is possible to prove identities using generating functions, so I would appreciate if you could help me prove this equality using generating functions (or in any way that is different from mine).

Answer 1

Since you were asking about generating functions, here's one using that: \begin{align*} \frac{1}{(1-x)}\cdot \frac{1}{(1-x)^k} &= \sum_{n\ge 0} \left(\sum_{i=0}^n \binom{i+k-1}{k-1}\right) x^n \\ \frac{1}{(1-x)^{k+1}} &= \sum_{n\ge 0} \binom{n+k}{k} x^n \\ \implies \sum_{i=0}^n \binom{i+k-1}{k-1} &= \binom{n+k}{k} \end{align*} hence completing the proof.

Notice that we have used \begin{align*} \frac{1}{(1-x)^k} &= \sum_{i\ge 0} \binom{i+k-1}{k-1}\, x^i \end{align*}