Manipulation of combinations 
Let $k,n\in\Bbb N_0$, with $k\le n$. Prove that
$$\binom{n+1}{k+1}=\sum_{j=0}^{n-k}\binom{n-j}k\;.$$

Just was hoping someone could give me a hint or two with this problem. I think it has to do with breaking apart the summation notation, but I'm a little stuck on how to do that.
Thanks!
 A: Consider the problem of choosing $k+1$ numbers from the set $\{0,1,2,\ldots,n\}$, all chosen numbers different, order not important.
Doing this in the obvious way, the number of choices is the LHS.
Now do it the following way.  First pick the smallest of the chosen numbers, call it $j$.  It could be anywhere from $0$ to $n-k$.  Then you have to pick $k$ further numbers from
$$\{j+1,j+2,\ldots,n\}\ ,$$
and in this set there are $n-j$ numbers to choose from.  Thus the total number of choices is the expression on the RHS.
Therefore LHS${}={}$RHS.
A: $\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\dsc}[1]{\displaystyle{\color{#c00000}{#1}}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,{\rm Li}_{#1}}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
We can always choose $\ds{a}$ such that $\ds{0\ <\ a}$ and
$\ds{\verts{z + 1}\ >\ 1}$ when $\ds{\verts{z}\ =\ a}$.

\begin{align}&\color{#66f}{\large\sum_{j\ =\ 0}^{n - k}{n-j \choose k}}
=\sum_{j\ =\ 0}^{\infty}\oint_{\verts{z}\ =\ a}
{\pars{1 + z}^{n - j} \over z^{k + 1}}\,{\dd z \over 2\pi\ic}
=\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n} \over z^{k + 1}}
\sum_{j\ =\ 0}^{\infty}\pars{1 \over 1 + z}^{j}\,{\dd z \over 2\pi\ic}
\\[5mm]&=\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n} \over z^{k + 1}}
{1 \over 1 - 1/\pars{1 + z}}\,{\dd z \over 2\pi\ic}
=\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n + 1} \over z^{k + 2}}
\,{\dd z \over 2\pi\ic}
=\color{#66f}{\large{n + 1 \choose k + 1}}
\end{align}

