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

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!

• Well $\sum_{i=1}^n{i\choose k}=\sum_{i=k}^n{i\choose k}$ anyway. – Jp McCarthy Jan 9 '15 at 13:33
• Do an example. Pick a $k$, e.g. $k = 10$. Pick an $n$, e.g. $n = 5$. Compute the first term. Compute the last term. Now repeat with another $n$, e.g. $n = 12$. – Hans Engler Jan 9 '15 at 13:42
• Jp McCarthy, can you pls explain how? – Harshal Gajjar Jan 9 '15 at 13:45
• Consider ${2\choose k}$ with $k=3$... that is ${2\choose3}$. Now from two items, how many ways can you choose three of them? Zero. So all of the terms up to but not including ${k\choose k}$ are zero... of course ${k\choose k}=1$. – Jp McCarthy Jan 9 '15 at 13:51
• I think you've missed the edit, I had (initially) placed wrong inequalities.. – Harshal Gajjar Jan 9 '15 at 13:55

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

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}

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...

• +1 for the answer, I would I'm going to start matrices day after tomorrow.. Would come back. :) – Harshal Gajjar Jan 9 '15 at 13:57

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

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.