Algebraic proof that $\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$ I'm looking for an algebraic proof of this identity for $n, k \in \mathbb{N}$:
$$\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$$
So far, I've turned the left hand side of the equality into $\frac{1}{k!}\sum\limits_{m=0}^{n-k} \frac{(m+k)!}{m!}$, but I got stuck there and can't get any further.
 A: Use induction on $n$.
The relation $\displaystyle\sum_{i=k}^n\binom ik=\binom{n+1}{k+1}$ is trivially verified if $n=1$ (and $k\le n$).
Suppose, by inductive hypothesis, the formula is true for some $n\ge 1$ and $k\le n$. Then
$$
\sum_{i=k}^{n+1}\binom ik=\sum_{i=k}^n\binom ik+\binom {n+1}k=\binom{n+1}{k+1}+\binom {n+1}k = \binom{n+2}{k+1}.
$$
If $k=n+1$, then the left-hand side is reduced to just one term: $\dbinom{n+1}{n+1}$, which is is equal to  $\dbinom{n+2}{n+2}$.
A: Let's examine $\displaystyle\sum_{k=0}^\infty\sum_{i=0}^n\binom{i}{k}x^k$. At the end, we'll look at the coefficient of $x^k$ to get our answer.
\begin{align}
\sum_{k=0}^\infty\sum_{i=0}^n\binom ikx^k&=\sum_{i=0}^n\sum_{k=0}^\infty\binom ikx^k\\
&=\sum_{i=0}^n(1+x)^i\\
&=\frac{(1+x)^{n+1}-1}{(1+x)-1}\\
&=\frac{(1+x)^{n+1}-1}{x}\\
&=\frac{\sum_{j=0}^\infty\binom{n+1}j x^j-1}x\\
&=\frac{\sum_{j=\color{Red} 1}^\infty\binom{n+1}j x^j}x\\
&=\sum_{j=1}^\infty\binom{n+1}j x^{j-1}\\
&=\sum_{k=0}^\infty\binom{n+1}{k+1}x^k\\
\sum_{i=0}^n\binom{i}{k}&=\binom{n+1}{k+1}
\end{align}
The first step is The Most Powerful Proof Technique in Mathematics: switching the order of summation. (Which is why I had to put the extra $\sum$ sign in there. I can't switch the order of summation without two summations there in the first place.)
The $x^k$ term is there so I can get back the answer at the end. If I hadn't put it in there, I would have just ended up with $2^{n+1}-1$ at the end, which isn't very helpful.
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
\sum_{i = 0}^{n}{i \choose k} & =
\sum_{i = 0}^{n}\bracks{z^{k}}\pars{1 + z}^{\, i} =
\bracks{z^{k}}\sum_{i = 0}^{n}\pars{1 + z}^{\, i} =
\bracks{z^{k}}{\pars{1 + z}^{n + 1} - 1 \over \pars{z + 1} - 1}
\\[5mm] & =
\bracks{z^{k + 1}}\pars{1 + z}^{n + 1} -
\bracks{z^{k + 1}}1 =
\bbx{\large{n + 1 \choose k + 1} - \delta_{k,-1}} \\ &
\end{align}
