How to find $ \binom {1}{k} + \binom {2}{k} + \binom{3}{k} + ... + \binom{n}{k} $

Question

Find $$ \binom {1}{k} + \binom{2}{k} + \binom{3}{k} + ... + \binom {n}{k} $$ if $0 \le k \le n$

Any method for solving this problem? I've not achieved anything so far. Thanks in advance!

Answer 1

For $k=0$, the answer is $n$.

For $k>0$, the answer is ${{n+1}\choose{k+1}}$.

This can be seen by considering how many ways there are to choose $k+1$ integers from the set $\{1,2,\dots,n+1\}$ and conditioning on the greatest integer chosen, because there have to be $k$ choices less than the greatest integer chosen.

For instance we look at ${{n+1}\choose{k+1}}={6\choose 4}$. To choose $4$ elements from $\{1,2,3,4,5,6\}$, the greatest chosen element could be $4$, and then we would have to choose $3$ elements from $\{1,2,3\}$; or the greatest chosen element could be $5$, and then we would have to choose $3$ elements from $\{1,2,3,4\}$; or the greatest chosen element could be $6$, and then we would have to choose $3$ elements from $\{1,2,3,4,5\}$.

So altogether, ${6\choose 4}={3\choose 3}+{4\choose 3}+{5\choose 3}$.

Note: the other terms in the sum, of the form ${i\choose k}$ with $i<k$, are all $0$.

Answer 2

No formal answer, but a nice illustration:
The solution can exemplarically be shown by a matrix-multiplication-scheme. The following shows $S \cdot P = X$, where $X$ is simply a shifting of $P$ .
The left-bottom is matrix $S$ which performs the partial summations of the columns of matrix $P$ which is in the right-top-matrix, and the result $X$ is the right-bottom-matrix: $$ \small \begin{matrix} . & . & . & . & . & | & 1 & . & . & . & . & | \\ . & . & . & . & . & | & 1 & 1 & . & . & . & | \\ . & . & . & . & . & | & 1 & 2 & 1 & . & . & | \\ . & . & . & . & . & | & 1 & 3 & 3 & 1 & . & | \\ . & . & . & . & . & | & 1 & 4 & 6 & 4 & 1 & | \\ - & - & - & - & - & + & - & - & - & - & - & + \\ 1 & . & . & . & . & | & 1 & . & . & . & . & | \\ 1 & 1 & . & . & . & | & 2 & 1 & . & . & . & | \\ 1 & 1 & 1 & . & . & | & 3 & 3 & 1 & . & . & | \\ 1 & 1 & 1 & 1 & . & | & 4 & 6 & 4 & 1 & . & | \\ 1 & 1 & 1 & 1 & 1 & | & 5 & 10 & 10 & 5 & 1 & | \\ - & - & - & - & - & + & - & - & - & - & - & + \end{matrix} $$

From this a hypothetical result can easily be formulated and gives the direction of the attempt of a proof...

Answer 3

You can prove by induction that

$$\binom {1}{k} + \binom{2}{k} + \binom{3}{k} + ... + \binom {n}{k}=\frac{(k-1)\binom{1}{k}+(n-k+1)\binom{n+1}{k}}{k+1}$$

holds for every value of $k$.

Answer 4

For a polynom $P(x)=a_mx^m +\dots +a_1x+a_0$ denote $[x^k]P(x)=a_k$.

Notice that for $k\le i \le n$ $$\dbinom{i}{k}=[x^k](1+x)^i$$ hence \begin{align} \sum_{i=1}^n\dbinom{i}{k}&=\sum_{i=k}^n\dbinom{i}{k}\\ &=\sum_{i=1}^n[x^k](1+x)^i\\ &=[x^k]\sum_{i=k}^n(1+x)^i\\ &=[x^k]\frac{(1+x)^{n+1}-(1+x)^k}{(1+x)-1}\\ &=[x^k]\frac{(1+x)^{n+1}-(1+x)^k}{x}\\ &=[x^{k+1}]\left((1+x)^{n+1}-(1+x)^k\right)\\ &=[x^{k+1}](1+x)^{n+1}+[x^{k+1}](1+x)^{k}\\ &=\dbinom{n+1}{k+1}+0\\ &=\dbinom{n+1}{k+1} \end{align}

Answer 5

The automatic solution: using the the Gosper's algorithm in Maxima: AntiDifference(binomial(i,k),i);

$$\binom{i}{k}=\frac{\binom{i}{k}\,\left(k-i\right)}{k+1}-\frac{\binom{i+1}{k}\,\left(k-(i+1)\right)}{k+1}$$ and the sum telescopes.