Let's give a combinatorial proof.
$\binom{n+1}{k+1}$ is the number of subsets of $[n] = \{0,1,2, \ldots, n\}$ having exactly $k+1$ elements. Looking at the smallest or largest element of such a subset makes sense.
Let's look at the second smallest element instead. It can be any number from $1$ (for subsets which have $0$ and $1$ as their two smallest elements) to $n-k+1$ (for subsets which have $n-k+1, \ldots, n-1, n$ as their $k$ largest elements).
So $$\binom{n+1}{k+1} = \sum_{i=1}^{n-k+1} \textrm{number of subsets having $i$ as 2nd smallest element}.$$
So how many $(k+1)$-element subsets of $[n]$ have $i$ as 2nd smallest elements?
Well, the recipe to make such a subset is clear:
- Chose any number in $0, 1, \ldots, i-1$ to serve as smallest element.
- Pick $i$ as second smallest element.
- Pick any $(k-1)$-element subset of $\{i+1, \ldots, n\}$ to serve as the $n-1$ elements larger than $i$.
In the first step, you have $i$ choices, the second step involves no choice and you have $\binom{n-i}{k-1}$ choices in the last step, because $\{i+1, \ldots, n\}$ has $n-i$ elements.
So the number of $(k+1)$-element subsets of $[n]$ having $i$ in second position is $i \binom{n-i}{k-1}$, which proves that
$$\binom{n+1}{k+1} = \sum_{i=1}^{n-k+1} i \binom{n-i}{k-1}.$$
A slight generalisation of this proof shows that if $a+b=k$
$$ \binom{n+1}{k+1} = \sum_i \binom{i}{a}\binom{n-i}{b}:$$
you only have to look at the $(a+1)$-th largest element of the $(k+1)$-element subsets of $n+1$. We have just done the $a=1$ case.
Best Answer
$\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{\on}[1]{\operatorname{#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} &\bbox[5px,#ffd]{\sum_{i = 0}^{b}\pars{-1}^{i} {b \choose i}{a + b - i - 1 \choose a - i}} \\[5mm] = &\ \sum_{i = 0}^{b}\pars{-1}^{i} {b \choose i}\bracks{z^{a - i}} \pars{1 + z}^{a + b - i - 1} \\[5mm] = &\ \bracks{z^{a}}\pars{1 + z}^{a + b - 1}\sum_{i = 0}^{b} {b \choose i}\pars{-\,{z \over 1 + z}}^{i} \\[5mm] = &\ \bracks{z^{a}}\pars{1 + z}^{a + b - 1}\,\, \pars{1 - {z \over 1 + z}}^{b} \\[5mm] = &\ \bracks{z^{a}}\pars{1 + z}^{a - 1} = \bbx{\large 0} \\ & \end{align}