Algebraic proof that $\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$

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

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.