1
$\begingroup$

Is this formula true?

$$ \sum_{m=k}^n {m \choose k}={n+1 \choose k+1} $$

If yes how to prove it?

$\endgroup$
  • 2
    $\begingroup$ What are your thoughts? What have you tried? $\endgroup$ – Sloan Mar 28 '15 at 14:46
  • $\begingroup$ Try induction on $n$ $\endgroup$ – Elaqqad Mar 28 '15 at 14:48
  • $\begingroup$ You can also do a combinatorial proof by counting the number of subsets of $\{0,\dots,n\}$ which have $k+1$ elements. In the first sum, $m$ is the largest element of the subset. $\endgroup$ – Michael Burr Mar 28 '15 at 14:49
  • $\begingroup$ I strongly believe this is a duplicate, now looking for it. $\endgroup$ – Jack D'Aurizio Mar 28 '15 at 15:07
  • $\begingroup$ Almost duplicate: math.stackexchange.com/questions/619940/… $\endgroup$ – Jack D'Aurizio Mar 28 '15 at 15:09
4
$\begingroup$

Combinatorial proof

Let $A=\{0,\cdots,n\}$. This set has $n+1$ elements, so $\begin{pmatrix}n+1\\k+1\end{pmatrix}$ counts the number of subsets of size $k+1$.

On the other hand, for any subset of size $k+1$, let $m$ be its largest element. It is certainly true that $k\leq m\leq n$. Since $\begin{pmatrix}m\\k\end{pmatrix}$ is the number of subsets of $\{0,\cdots,m-1\}$ with $k$ elements, it is also the number of subsets of $\{0,\cdots,n\}$ with $k+1$ elements and $m$ as the largest element.

These two counts count the same thing, and, therefore, are equal.

$\endgroup$
1
$\begingroup$

there is also a straightforward inductive proof based on $$ \sum_{m=k}^{n+1} {m \choose k}= \sum_{m=k}^n {m \choose k}+{n+1 \choose k} = {n+1 \choose k+1}+{n+1 \choose k}={n+2 \choose k+1} $$

$\endgroup$
0
$\begingroup$

Observe that when we introduce the integral representation $${m\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{k+1}}\; dz$$

we get for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{m=k}^n \frac{(1+z)^m}{z^{k+1}}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \sum_{m=k}^n (1+z)^m \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \frac{(1+z)^{n+1}-(1+z)^k}{1+z-1} \;dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+2}} \left((1+z)^{n+1}-(1+z)^k\right) \; dz.$$

This has two pieces, the first of which is $${n+1\choose k+1}$$ and the second, which is zero, thus concluding the proof.

This MSE link has another computation in the same spirit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.