Vtyjkyuk

Imagine the first $n + 1$ numbers, written in order on a piece of paper. The right hand side asks in how many ways you can pick $k+1$ of them. In how many ways can you do this?

You first pick a highest number, which you circle. Call it $s$. Next, you still have to pick $k$ numbers, each less than $s$, and there are $binoms - 1k$ ways to do this.

Since $s$ is ranging from $1$ to $n$, $t:= s-1$ is ranging from $0$ to $n$ as desired.

$$beginalign
sum_t=colorblue0^n binomtk =sum_t=colorbluek^nbinom tk&= sum_t=k^nleft[ binom t+1k+1-binom tk+1right]\
&=sum_t=colororangek^colororangenbinom colororanget+1k+1-sum_t=k^nbinom tk+1\
&=sum_t=colororangek+1^colororangen+1binom colororangetk+1-sum_t=k^nbinom tk+1\
&=binomn+1k+1-underbracebinom kk+1_0&&textby telescoping\
&=binomn+1k+1quadblacksquare\
endalign$$

We can use the well known identity
$$1+x+dots+x^n = fracx^n+1-1x-1.$$
After substitution $x=1+t$ this becomes
$$1+(1+t)+dots+(1+t)^n=frac(1+t)^n+1-1t.$$
Both sides of these equations are polynomials in $t$. (Notice that the RHS simplifies to $sum_j=1^n+1binom n+1j t^j-1$.)

If we compare coefficient of $t^k$ on the LHS and the RHS we see that
$$binom 0k + binom 1k + dots + binom nk = binomn+1k+1.$$

---

This proof is basically the same as the proof using generating functions, which was posted in other answers. However, I think it is phrased a bit differently. (And if it is formulated this way, even somebody who has never heard of generating functions can follow the proof.)

You can use induction on $n$, observing that

$$
sum_t=0^n+1 binomtk
= sum_t=0^n binomtk + binomn+1k
= binomn+1k+1 + binomn+1k
= binomn+2k+1
$$

The RHS is the number of $k+1$ subsets of $1,2,...,n+1$. Group them according to the largest element in the subset. Sum up all the cases. Get the LHS.

Another technique is to use snake oil. Call your sum:

$beginalign
S_k
&= sum_0 le t le n binomtk
endalign$

Define the generating function:

$beginalign
S(z)
&= sum_k ge 0 S_k z^k \
&= sum_k ge 0 z^k sum_0 le t le n binomtk \
&= sum_0 le t le n sum_k ge 0 binomtk z^k \
&= sum_0 le t le n (1 + z)^t \
&= frac(1 + z)^n + 1 - 1(1 + z) - 1 \
&= z^-1 left( (1 + z)^n + 1 - 1 right)
endalign$

So we are interested in the coefficient of $z^k$ of this:

$beginalign
[z^k] z^-1 left( (1 + z)^n + 1 - 1 right)
&= [z^k + 1] left( (1 + z)^n + 1 - 1 right) \
&= binomn + 1k + 1
endalign$

We can use the integral representation of the binomial coefficient $$dbinomtk=frac12pi ioint_zrightfracleft(1+zright)^tz^k+1dztag1
$$ and get $$sum_t=0^ndbinomtk=frac12pi ioint_zrightfracsum_k=0^nleft(1+zright)^tz^k+1dz
$$ $$=frac12pi ioint_zrightfracleft(z+1right)^n+1z^k+2dz-frac12pi ioint_zrightfrac1z^k+2dz
$$ and so usign again $(1)$ we have $$sum_t=0^ndbinomtk=dbinomn+1k+1-0=colorreddbinomn+1k+1.$$

You remember that:
$$
(1+x)^m = sum_k binommk x^k
$$
So the sum
$$
sum_m=0^M binomm+kk
$$
is the coefficient of $ x^k $ in:
$$
sum_m=0^M (1+x)^m+k
$$ Yes?
So now use the geometric series formula given:
$$
sum_m=0^M (1+x)^m+k = -frac(1+x)^kx left( 1 - (1+x)^M+1 right)
$$
And now you want to know what is coefficient of $x^k $ in there. You got it from here.

In this answer, I prove the identity
$$
binom-nk=(-1)^kbinomn+k-1ktag1
$$
Here is a generalization of the identity in question, proven using the Vandermonde Identity
$$
beginalign
sum_m=0^Mbinomm+kkbinomM-mn
&=sum_m=0^Mbinomm+kmbinomM-mM-m-ntag2\
&=sum_m=0^M(-1)^mbinom-k-1m(-1)^M-m-nbinom-n-1M-m-ntag3\
&=(-1)^M-nsum_m=0^Mbinom-k-1mbinom-n-1M-m-ntag4\
&=(-1)^M-nbinom-k-n-2M-ntag5\
&=binomM+k+1M-ntag6\
&=binomM+k+1n+k+1tag7
endalign
$$
Explanation:

$(2)$: $binomnk=binomnn-k$

$(3)$: apply $(1)$ to each binomial coefficient

$(4)$: combine the powers of $-1$ which can then be pulled out front

$(5)$: apply Vandermonde

$(6)$: apply $(1)$

$(7)$: $binomnk=binomnn-k$

To get the identity in the question, set $n=0$.

Recall that for $kinBbb N$ we have the generating function

$$sum_nge 0binomn+kkx^n=frac1(1-x)^k+1;.$$

The identity in the question can therefore be rewritten as

$$left(sum_nge 0binomn+kkx^nright)left(sum_nge 0x^nright)=sum_nge 0binomn+k+1k+1x^n;.$$

The coefficient of $x^n$ in the product on the left is

$$sum_i=0^nbinomi+kkcdot1=sum_i=0^nbinomi+kk;,$$

and the $n$-th term of the discrete convolution of the sequences $leftlanglebinomn+kk:ninBbb Nrightrangle$ and $langle 1,1,1,dotsrangle$. And at this point you’re practically done.

A standard technique to prove such identities $sum_i=0^Mf(i)=F(M)$, involving on one hand a sum where only the upper bound $M$ is variable and on the other hand an explicit expression in terms of$~M$, is to use induction on$~M$. It amounts to showing that $f(M)=F(M)-F(M-1)$ (and that $F(0)=f(0)$). This is similar to using the fundamental theorem of calculus in showing that $int_0^x_0f(x)mathrm dx=F(x_0)$ by establishing $f(x)=F'(x)$ (and $F(0)=0$).

So here you need to check (apart from the obvious starting case $M=0$) that $binomM+kk=binomM+k+1k+1-binomM+kk+1$. This is just in instance of Pascal's recurrence for binomial coefficients.

$newcommandangles[1]leftlangle,#1,rightrangle
newcommandbraces[1]leftlbrace,#1,rightrbrace
newcommandbracks[1]leftlbrack,#1,rightrbrack
newcommandddmathrmd
newcommandds[1]displaystyle#1
newcommandexpo[1],mathrme^#1,
newcommandhalf1 over 2
newcommandicmathrmi
newcommandiffLeftrightarrow
newcommandimpLongrightarrow
newcommandol[1]overline#1
newcommandpars[1]left(,#1,right)
newcommandpartiald[3]fracpartial^#1 #2partial #3^#1
newcommandroot[2],sqrt[#1],#2,,
newcommandtotald[3]fracmathrmd^#1 #2mathrmd #3^#1
newcommandverts[1]leftvert,#1,rightvert$
Assuming $dsM geq 0$:

beginequation
mboxNote thatquad
sum_m = 0^Mm + k choose k = sum_m = k^M + km choose k =
a_M + k - a_k - 1quadmboxwherequad a_n equiv
sum_m = 0^nm choose ktag1
endequation

---

Then,
beginalign
color#f00a_n & equiv sum_m = 0^nm choose k =
sum_m = 0^n overbrace%
oint_vertsz = 1pars1 + z^m over z^k + 1,dd z over 2piic
^dsm choose k =
oint_vertsz = 11 over z^k + 1sum_m = 0^npars1 + z^m
,dd z over 2piic
\[3mm] & =
oint_vertsz = 11 over z^k + 1,
pars1 + z^n + 1 - 1 over pars1 + z - 1,dd z over 2piic =
underbraceoint_vertsz = 1pars1 + z^n + 1 over z^k + 2
,dd z over 2piic_dsn + 1 choose k + 1 -
underbraceoint_vertsz = 11 over z^k + 2,dd z over 2piic
_dsdelta_k + 2,1
\[8mm] imp color#f00a_n & = fbox$dsquad%
n + 1 choose k + 1 - delta_k,-1quad$
endalign

---

beginalign
mboxWith pars1,,quad
color#f00sum_m = 0^Mm + k choose k & =
bracksM + k + 1 choose k + 1 - delta_k,-1 -
bracksk choose k + 1 - delta_k,-1
\[3mm] & =
M + k + 1 choose k + 1 - k choose k + 1
endalign
Thanks to $ds@robjohn$ user who pointed out the following feature:
$$
k choose k + 1 = -k + k + 1 - 1 choose k + 1pars-1^k + 1 =
-pars-1^k0 choose k + 1 = delta_k,-1
$$
such that
$$
beginarrayhlinembox\
dsquadcolor#f00sum_m = 0^Mm + k choose k =
color#f00M + k + 1 choose k + 1 - delta_k,-1quad
\ mbox\ hline
endarray
$$