Calculate sum $S=\sum_{k=0}^{n}\binom{k}m$ Calculate sum $$S=\sum_{k=0}^{n}\begin{pmatrix} k \\ m\end{pmatrix}$$
My solution


*

*if $n<m$, $S=0$

*else $$S=\sum_{k=0}^{n}\binom{k}m=\sum_{k=m}^{n}\begin{pmatrix} k \\ m\end{pmatrix}=\frac{1}{m!}\left(m!+\frac{(m+1)!}{1!}+\frac{(m+2)!}{2!}+...\frac{n!}{(n-m)!}\right)$$


come here, I don't know what to do.
 A: Assume $n\ge m$. We have $n+1$ different doughnuts, labelled $1$ to $n+1$, lined up in a row, and want to choose $m+1$ of them for a healthy breakfast. There are $\binom{n+1}{m+1}$ ways to do it. Let us count the number of breakfast choices  another way.
Let $j$ be the number of the first (leftmost) doughnut chosen.
If $j=1$, we need to choose $m$ doughnut from the remaining $n$, and there are $\binom{n}{m}$ ways to do it.
If $j=2$, we need to choose $m$ doughnuts from the remaining $n-1$, and there are $\binom{n-1}{m}$ ways to do it.
And so on. We obtain our sum, backwards.
A: Hint: find the generating function with respect to $m$.
A: $$S=\sum_{k=0}^{n}\begin{pmatrix} k \\ m\end{pmatrix}=\sum_{k=m}^{n}\begin{pmatrix} k \\ m\end{pmatrix}$$$$=\sum_{k=m}^{n}\left[\binom{k+1}{m+1}-\binom{k}{m+1}\right]$$$$=\color{blue}{\sum_{k=m}^{n}\binom{k+1}{m+1}}-\sum_{k=m}^{n}\binom{k}{m+1}$$
Setting $k+1 \mapsto k$ on the blue part follows:
$$=\sum_{k=m+1}^{n+1}\binom{k}{m+1}-\sum_{k=m}^{n}\binom{k}{m+1}$$$$=\sum_{k=m+1}^{n}\binom{k}{m+1}-\sum_{k=m+1}^{n}\binom{k}{m+1}+\binom{n+1}{m+1}$$
So:
$$S=\bbox[5px,border:2px solid #00A000]{\sum_{k=0}^{n}\begin{pmatrix} k \\ m\end{pmatrix}=\binom{n+1}{m+1}}$$
