1
$\begingroup$

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:

enter image description here

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This isn't a 'story proof' the OP is looking for. $\endgroup$ – Simon S Dec 2 '14 at 14:09
  • $\begingroup$ 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... $\endgroup$ – idm Dec 2 '14 at 14:43
0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ This is a story written in Latin. $\endgroup$ – hengxin Dec 2 '14 at 15:04
  • $\begingroup$ @hengxin This is a distributed and formal story. $\endgroup$ – Felix Marin Dec 2 '14 at 15:05
  • $\begingroup$ 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. $\endgroup$ – hengxin Dec 2 '14 at 15:11
  • $\begingroup$ @hengxin It's a formal proof. Thanks for take your time to read it. $\endgroup$ – Felix Marin Dec 2 '14 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.