"Story" proof of $\sum_{i=j}^n {i \choose j} = {n+1 \choose j+1}$ I am reading a book "Discrete Mathematics for Computer Scientists". One of the exercises asks for a "story" proof of this: $\sum_{i=j}^n {i \choose j} = {n+1 \choose j+1}$.
My question is that:


*

*What is a story proff?

*What is the story proof of this identity?


Screenshot of the book:

 A: If you read ${n+1} \choose{j+1}$ as: You have $n+1$ numbered boxes $\{1,...,n+1\}$ and you want to place $j+1$ indistinguishable balls in these boxes (at most one in a box), how many ways is that possible . 
Then we look at different cases: To do this look at $x$ defined as the highest number for which the box is occupied. Note $x>j$ since all balls must be placed. This means that the other $j$ balls are distributed in the boxes $\{1,...,x-1\}$. This can be done in ${x-1} \choose {j}$ ways. Now we can sum $x$ over ${j+1,...,n+1}$. Therefor we get $\sum _{i=j}^n {i\choose j}={n+1 \choose j+1}$.   
A: $$\binom{n+1}{j+1}$$ is the number of subset with $j+1$ element of a set with $n+1$ element. Let $E$ a set with $n$ element. Let $a\in E$. The number of subset of with $j+1$ element contain $a$ are $\binom{n}{j}$ and the number of subset that doesn't contain $a$ are $\binom{n}{j+1}$. Then 
$$\binom{n+1}{j+1}=\binom{n}{j}+\binom{n}{j+1}$$
By reccursion, 
$$\binom{n}{j+1}=\binom{n-1}{j+1}+\binom{n-1}{j}$$
And at the end, you'll get
$$\binom{n+1}{j+1}=\sum_{i=j}^n\binom{i}{j}+\underbrace{\binom{j}{j+1}}_{=0}=\sum_{i=j}^n\binom{i}{j}$$
A: $\binom{n+1}{k+1}$ means the number of ways I can select $k+1$ objects from $n+1$ given objects. To do this, it means I select an object to begin with and then select $k$ elements which come before that object. I can do this because the collections with elements after that object are simply the collections with elements before some later element.
Expanding on this, we can write: the number of ways I can select $k+1$ objects from $n+1$ given objects is


*

*number of ways I can choose $k$ after choosing the $(k+1)$th element OR

*number of ways I can choose $k$ after choosing the $(k+2)$th element OR

*number of ways I can choose $k$ after choosing the $(k+3)$th element OR

*$\cdots$

*number of ways I can choose $k$ after choosing the $(k+(n-k))$th element


Which is just the `story' form of
$$\sum_{i=j}^n {i \choose j} = {n+1 \choose j+1}$$
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{\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}$
\begin{align}&\color{#66f}{\large\sum_{k\ =\ j}^{n}{k \choose j}}
=\sum_{k\ =\ j}^{n}\oint_{\verts{z}\ =\ 1}
{\pars{1 + z}^{k} \over z^{j + 1}}\,{\dd z \over 2\pi\ic}
=\oint_{\verts{z}\ =\ 1}
{1 \over z^{j + 1}}\sum_{k\ =\ j}^{n}\pars{1 + z}^{k}\,{\dd z \over 2\pi\ic}
\\[5mm]&=\oint_{\verts{z}\ =\ 1}{1 \over z^{j + 1}}\,\pars{1 + z}^{j}\,
{\pars{1 + z}^{n - j + 1} - 1 \over \pars{1 + z} - 1}\,{\dd z \over 2\pi\ic}
\\[5mm]&=\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n + 1}\over z^{j + 2}}
\,{\dd z \over 2\pi\ic}
-\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{j}\over z^{j + 2}}
\,{\dd z \over 2\pi\ic}
={n + 1 \choose j + 1} -\
\underbrace{j \choose j + 1}_{\ds{=\ \color{#c00000}{0}}}\ = \
\color{#66f}{\large{n + 1 \choose j + 1}}
\end{align}
