# Give the combinatorial proof of the identity $\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$

Given the identity

$$\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$$

Need to give a combinatorial proof

a) in terms of subsets

b) by interpreting the parts in terms of compositions of integers

I should not use induction or any other ways...

-

HINTS:

1. Consider a $k$-element subset of $[n+k]=\{1,\dots,n+k\}$; it has a maximum element, which can be anything from $k$ through $n+k$. How many such subsets are there with maximum element $k+i$ for $i=0,\dots,n$?

2. There are $\binom{k-1+i}{k-1}$ compositions of $k+i$ with $k$ terms. There are $\binom{n+k}k$ compositions of $n+k+1$ with $k+1$ terms.

-
2)Let's split n+k into two parts: 1 and n+k-1. including 1, we have $\binom{n+k-1}{k-1}$, otherwise $\binom{n+k-1}{k}$. Hence $\binom{n+k}{k}$= $\binom{n+k-1}{k-1}$+$\binom{n+k-1}{k}$ Using $\binom{n+k-1}{k}$,repeat the procedure till $\binom{k-1}{k-1}$. 1)I'm still confused here. I understand that the answer to your question should be the identity, however I don't quite understand how this works. – John Lennon Mar 5 '13 at 22:09
(1) Oops: the maximum should have been $k+i$, not $k-1+i$. If $k+i$ is the maximum element of a $k$-element subset of $[n+k]$, the other $k-1$ elements can be any $k-1$ elements of the set $[k-1+i]$, and there are $\binom{k-1+i}{k-1}$ of them. Thus, the summation is just counting the $k$-element subsets of $n+k$ in groups corresponding to their maximum elements. (2) You’re suggesting an informal proof by induction, not a combinatorial argument. You do not want an argument by induction; you want to show that the two sides are counting the same set of compositions in two different ways. – Brian M. Scott Mar 5 '13 at 22:15
"There are $\binom{k-1+i}{k-1}$ compositions of $k+i$ with $k$ terms. There are $\binom{n+k}k$ compositions of $n+k+1$ with $k+1$ terms." Is this already an answer? If so could you explain it to me? – John Lennon Mar 19 '13 at 23:20
@vercammen: Suppose that you have a composition of $n+k+1$ with $k+1$ terms; when you throw away the last term, what’s left is a composition with $k$ terms of some number between $k$ and $k+n$ inclusive. – Brian M. Scott Mar 19 '13 at 23:30
finally clear. thank you! – John Lennon Mar 19 '13 at 23:42

Use $\binom{k}{r} = \binom{k-1}{r} + \binom {k-1}{r-1}$ repeatedly on the expansion of sum.

-

$\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{\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]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \color{#f00}{\sum_{j = 0}^{n}{k - 1 + j \choose k - 1}} & = \sum_{j = 0}^{n}{k - 1 + j \choose j} = \sum_{j = 0}^{n}{-k + 1 - j + j - 1 \choose j}\pars{-1}^{j} = \sum_{j = 0}^{n}{-k \choose j}\pars{-1}^{j} \\[3mm] & = \sum_{j = -\infty}^{n}{-k \choose j}\pars{-1}^{j} = \sum_{j = -n}^{\infty}{-k \choose -j}\pars{-1}^{-j} = \sum_{j = 0}^{\infty}{-k \choose n - j}\pars{-1}^{j + n} = \\[3mm] & = \pars{-1}^{n}\sum_{j = 0}^{\infty}\pars{-1}^{j}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{-k} \over z^{n - j + 1}}\,{\dd z \over 2\pi\ic} \\[3mm] & = \pars{-1}^{n}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{-k} \over z^{n + 1}}\sum_{j = 0}^{\infty}\pars{-z}^{j} \,{\dd z \over 2\pi\ic} = \pars{-1}^{n}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{-k - 1} \over z^{n + 1}}\,{\dd z \over 2\pi\ic} \\[3mm] & = \pars{-1}^{n}{-k - 1 \choose n} = \pars{-1}^{n}{k + 1 + n - 1 \choose n}\pars{-1}^{n} = {n + k \choose n} = \color{#f00}{n + k \choose k} \end{align}

-