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!

  • 2
    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
up vote 3 down vote accepted

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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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