# “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:

1. What is a story proff?
2. What is the story proof of this identity?

Screenshot of the book:

• I would assume they mean a combinatorial proof. – Math1000 Dec 2 '14 at 12:33
• See math.stackexchange.com/questions/1038606/… for a similar request. – lhf Dec 2 '14 at 12:38
• @lhf I saw that but I still don't understand what it is? – Kartik Dec 2 '14 at 12:39
• See the "story" about "choosing a committee". – lhf Dec 2 '14 at 12:40
• May this help. – user 170039 Dec 2 '14 at 12:41

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}$.

$$\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}$$

• This isn't a 'story proof' the OP is looking for. – Simon S Dec 2 '14 at 14:09
• It's not complicate to adapte it to a story. Juste define $n+1$ balls with $n+1$ different color, and to count the possibilities the combinaison that doesn't contain $j$ color... – idm Dec 2 '14 at 14:43

$\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}$$


\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}

• This is a story written in Latin. – hengxin Dec 2 '14 at 15:04
• @hengxin This is a distributed and formal story. – Felix Marin Dec 2 '14 at 15:05
• I think it must be amazing. But I am not able to read it (I am not good at maths and handling with symbols. Ignore me.). Maybe you are willing to write a story about this story. – hengxin Dec 2 '14 at 15:11
• @hengxin It's a formal proof. Thanks for take your time to read it. – Felix Marin Dec 2 '14 at 15:12