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!
 A: 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$.
A: 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}
A: 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... 
A: 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$.
A: 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.
