1

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.

Thomas Andrews
  • 177,126
Bosen
  • 21

3 Answers3

1

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.

André Nicolas
  • 507,029
0

Hint: find the generating function with respect to $m$.

Robert Israel
  • 448,999
0

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