Jtdylktuy

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 $binom{s - 1}{k}$ ways to do this.

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

$$begin{align}
sum_{t=color{blue}0}^n binom{t}{k} =sum_{t=color{blue}k}^nbinom tk&= sum_{t=k}^nleft[ binom {t+1}{k+1}-binom {t}{k+1}right]\
&=sum_{t=color{orange}k}^color{orange}nbinom {color{orange}{t+1}}{k+1}-sum_{t=k}^nbinom t{k+1}\
&=sum_{t=color{orange}{k+1}}^{color{orange}{n+1}}binom {color{orange}{t}}{k+1}-sum_{t=k}^nbinom t{k+1}\
&=binom{n+1}{k+1}-underbrace{binom k{k+1}}_0&&text{by telescoping}\
&=binom{n+1}{k+1}quadblacksquare\
end{align}$$

We can use the well known identity
$$1+x+dots+x^n = frac{x^{n+1}-1}{x-1}.$$
After substitution $x=1+t$ this becomes
$$1+(1+t)+dots+(1+t)^n=frac{(1+t)^{n+1}-1}t.$$
Both sides of these equations are polynomials in $t$. (Notice that the RHS simplifies to $sum_{j=1}^{n+1}binom {n+1}j 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 = binom{n+1}{k+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} binom{t}{k}
= sum_{t=0}^{n} binom{t}{k} + binom{n+1}{k}
= binom{n+1}{k+1} + binom{n+1}{k}
= binom{n+2}{k+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:

$begin{align}
S_k
&= sum_{0 le t le n} binom{t}{k}
end{align}$

Define the generating function:

$begin{align}
S(z)
&= sum_{k ge 0} S_k z^k \
&= sum_{k ge 0} z^k sum_{0 le t le n} binom{t}{k} \
&= sum_{0 le t le n} sum_{k ge 0} binom{t}{k} 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)
end{align}$

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

$begin{align}
[z^k] z^{-1} left( (1 + z)^{n + 1} - 1 right)
&= [z^{k + 1}] left( (1 + z)^{n + 1} - 1 right) \
&= binom{n + 1}{k + 1}
end{align}$

We can use the integral representation of the binomial coefficient $$dbinom{t}{k}=frac{1}{2pi i}oint_{left|zright|=1}frac{left(1+zright)^{t}}{z^{k+1}}dztag{1}
$$ and get $$sum_{t=0}^{n}dbinom{t}{k}=frac{1}{2pi i}oint_{left|zright|=1}frac{sum_{k=0}^{n}left(1+zright)^{t}}{z^{k+1}}dz
$$ $$=frac{1}{2pi i}oint_{left|zright|=1}frac{left(z+1right)^{n+1}}{z^{k+2}}dz-frac{1}{2pi i}oint_{left|zright|=1}frac{1}{z^{k+2}}dz
$$ and so usign again $(1)$ we have $$sum_{t=0}^{n}dbinom{t}{k}=dbinom{n+1}{k+1}-0=color{red}{dbinom{n+1}{k+1}.}$$

You remember that:
$$
(1+x)^m = sum_k binom{m}{k} x^k
$$
So the sum
$$
sum_{m=0}^M binom{m+k}{k}
$$
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)^k}{x} 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{-n}{k}=(-1)^kbinom{n+k-1}{k}tag{1}
$$
Here is a generalization of the identity in question, proven using the Vandermonde Identity
$$
begin{align}
sum_{m=0}^Mbinom{m+k}{k}binom{M-m}{n}
&=sum_{m=0}^Mbinom{m+k}{m}binom{M-m}{M-m-n}tag{2}\
&=sum_{m=0}^M(-1)^mbinom{-k-1}{m}(-1)^{M-m-n}binom{-n-1}{M-m-n}tag{3}\
&=(-1)^{M-n}sum_{m=0}^Mbinom{-k-1}{m}binom{-n-1}{M-m-n}tag{4}\
&=(-1)^{M-n}binom{-k-n-2}{M-n}tag{5}\
&=binom{M+k+1}{M-n}tag{6}\
&=binom{M+k+1}{n+k+1}tag{7}
end{align}
$$
Explanation:

$(2)$: $binom{n}{k}=binom{n}{n-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)$: $binom{n}{k}=binom{n}{n-k}$

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

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

$$sum_{nge 0}binom{n+k}kx^n=frac1{(1-x)^{k+1}};.$$

The identity in the question can therefore be rewritten as

$$left(sum_{nge 0}binom{n+k}kx^nright)left(sum_{nge 0}x^nright)=sum_{nge 0}binom{n+k+1}{k+1}x^n;.$$

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

$$sum_{i=0}^nbinom{i+k}kcdot1=sum_{i=0}^nbinom{i+k}k;,$$

and the $n$-th term of the discrete convolution of the sequences $leftlanglebinom{n+k}k: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_0}f(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 $binom{M+k}k=binom{M+k+1}{k+1}-binom{M+k}{k+1}$. This is just in instance of Pascal's recurrence for binomial coefficients.

$newcommand{angles}[1]{leftlangle,{#1},rightrangle}
newcommand{braces}[1]{leftlbrace,{#1},rightrbrace}
newcommand{bracks}[1]{leftlbrack,{#1},rightrbrack}
newcommand{dd}{mathrm{d}}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{expo}[1]{,mathrm{e}^{#1},}
newcommand{half}{{1 over 2}}
newcommand{ic}{mathrm{i}}
newcommand{iff}{Leftrightarrow}
newcommand{imp}{Longrightarrow}
newcommand{ol}[1]{overline{#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]{leftvert,{#1},rightvert}$
Assuming $ds{M geq 0}$:

begin{equation}
mbox{Note that}quad
sum_{m = 0}^{M}{m + k choose k} = sum_{m = k}^{M + k}{m choose k} =
a_{M + k} - a_{k - 1}quadmbox{where}quad a_{n} equiv
sum_{m = 0}^{n}{m choose k}tag{1}
end{equation}