1
$\begingroup$

$$\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \dotsb + \binom{n}{r} = \binom{n+1}{r+1}$$

I don't have much experience with combinatorial proofs, so I'm grateful for all the hints.

(Presumptive) Source: Theoretical Exercise 1.11, P18, A First Course in Pr, 8th Ed, by S Ross

$\endgroup$
9
  • $\begingroup$ @MarcvanLeeuwen: Could you please let me know what may be wrong with the change of variables from that post to this post? With $\color{green}{m} = r$ and $$\color{green}{n} = n - r : \color{green}{\mathsf{\sum_{m \le i \le n} \binom{m+i}{m} = \binom{m+n+1}{m+1}}} \iff {\sum_{r \le i \le \color{red}{n - r}}\binom{r+i}{r} = \binom{n+1}{r+1}}. $$ But the summation inequality of the right one (in red) isn't $r \le i \le n$ ? $\endgroup$
    – user53259
    Nov 17, 2013 at 12:27
  • $\begingroup$ @LePressentiment: Although that post states it in words, in formula it gives $$\sum_{0\leq i\leq n'}\binom{m'+i}{m'}=\binom{m'+n'+1}{m'+1}. $$ Setting $m'=r$ and $n'=n-r$ gives $$\sum_{0\leq i\leq n-r}\binom{r+i}r=\binom{n+1}{r+1}, $$ which is the (first and originally only) formula of this question. You were wrong in assuming $m\leq i$ (in green, which becomes $r\leq i$) as the number ($i$) of letters B is only bounded above (by $n$), not below. $\endgroup$
    – Marc van Leeuwen
    Nov 17, 2013 at 21:59
  • $\begingroup$ I've rolled back the question, as I don't see any reason to suppose any particular source for this standard identity, not associate Fermat with it, and the added formula was garbled. If you want a formal summation, either the last one in my previous comment or $\sum_{k=r}^n\binom kr=\binom{n+1}{r+1}$ are possible, but adding it does not really illuminate the question much. $\endgroup$
    – Marc van Leeuwen
    Nov 17, 2013 at 22:07
  • $\begingroup$ @MarcvanLeeuwen: Thank you. Admittedly, I erred in associating the above with Brian M. Scott's comment. In math.stackexchange.com/a/65958/53259, TMM writes: $$\sum_{i=0}^{n} \binom{m+i}{i} = \binom{n + m + 1}{n} \quad \text{ where }0 \le \color{ #E87600}{i \le n}. $$ Could you please explicate how this is the same as the sum in your comment above where $ 0 \le \color{ #E87600}{i \le n - r}$? $\endgroup$
    – user53259
    Nov 18, 2013 at 6:10
  • $\begingroup$ @MarcvanLeeuwen: About the edit, I'll be happy to move the other info into my Answer. However, I readded the name and a source of the identity because I sustained whopping difficulty in lighting upon this qn. Had either been publicised, the search engine likely would've guided me here < 30 seconds, far less than the > 5 mins endured. Please let me know of any concerns. $\endgroup$
    – user53259
    Nov 18, 2013 at 6:21

4 Answers 4

Reset to default
11
$\begingroup$

Think about it this way:

The RHS counts the number of $(r+1)$-element subsets of $[n+1]$; while the LHS counts the same, though seperated into different cases: First of all there's ${r\choose r}$ subsets of $[n+1]$ that have $r+1$ elements with largest element $r+1$; then, there're ${r+1\choose r}$ subsets of $[n+1]$ that have $r+1$ elements with largest elements $r+2$; etc.

Therefore ...

$\endgroup$
0
$\begingroup$

This is analogous to https://math.stackexchange.com/a/357087/53259. The RHS here imports the number of ways of picking $r+1$ numbers out of $\{1,2,...,\color{magenta}{r}, \color{green}{r +1},...,\underbrace{n}_{= \color{magenta}{r} + (n - r)},\color{green}{n +1}\} \qquad (*)$

Now for any given choice of $r+1$ numbers, call the highest number chosen $k$ and esteem it as the $(r + 1)$th number. Observe :
The "leftmost" subset of $(*)$ containing $r + 1$ elements $ = \{1, 2, ..., r, \color{green}{r +1}\},$
Also, the "rightmost" subset of $(*)$ containing $r + 1$ elements $ = \{\color{green}{n +1} - (r + 1), ..., n , \color{green}{n +1}\}.$
Thus, $\color{green}{r +1} \leq k \leq \color{green}{n +1}$.

For each $k \in [\color{green}{r +1}, \color{green}{n +1}]$. , we must select the remaining $r$ numbers to be chosen
from the $k-1$ numbers smaller than $k$.

For $k = r +1$, must pick $r$ numbers to the left of $r + 1$, out of $\{\color{ #0073CF}{1, 2, ..., r}, r+1\}$.
Since there are $ \color{#0073CF}{r}$ such numbers, so $\color{#0073CF}{r}$ possible choices for $r$.
Thus the total number of choices for $r$ numbers $= \binom{\color{#0073CF}{r}}{r}$.

For $k = r +2$, must pick $r$ numbers to the left of $r + 2$, out of $\{\color{ #0073CF}{1, 2, ..., r, r +1}, r+2\}$.
Since there are $ \color{#0073CF}{r + 1}$ such numbers, so $\color{#0073CF}{r + 1}$ possible choices for $r$.
Thus the total number of choices for $r$ numbers $= \binom{\color{#0073CF}{r + 1}}{r}$.

...

For $k = n$, must pick $r$ numbers to the left of $n$, out of $\{\color{ #0073CF}{1, 2, ..., r, r + 1, ..., n - 1}, n\}$.
Since there are $ \color{#0073CF}{n - 1}$ such numbers, so $\color{#0073CF}{n - 1}$ possible choices for $r$.
Thus the total number of choices for $m$ numbers $= \binom{\color{#0073CF}{n - 1}}{r}$.

For $k = n + 1$, must pick $r$ numbers to the left of $n + 1$, out of $\{\color{ #0073CF}{1, 2, ..., r, r + 1, ..., n}, n + 1\}$.
Since there are $ \color{#0073CF}{n}$ such numbers, so $\color{#0073CF}{n}$ possible choices for $r$.
Thus the total number of choices for $m$ numbers $= \binom{\color{#0073CF}{n}}{r}$.

Summing up the number of ways of doing this for $k=r+1,...,r+n+1$ yields the LHS.

Remark : (Presumptive) Source: Theoretical Exercise 1.11, P18, A First Course in Pr, 8th Ed, by S Ross, via: $\color{blue}{\mathsf{i \text{ there }}}$ $ = i + 1$ here, $k$ there $= r + 1$ here, $\color{blue}{\mathsf{n \text{ there }}}$ $ = n + 1$ here.

$$\begin{align} \binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \dotsb + \binom{n}{r} &= \binom{n+1}{r+1} \\ \sum_{\Large{r \le i \le n \text{ or } i \in [r,n]}} \binom{i}{r}, n \ge r & =\end{align}$$

$\endgroup$
2
  • $\begingroup$ The two conditions under the summation are contradictory (it should be $r\leq i\leq n$), and in any case one condition suffices. The trailing ",n\geqr={}$' seems to be spurious too. Why do you presume this particular source(especially since the naming does not match exactly)? This identity must be present in some form or other in many, many texts on the subject. (But I admit Googling on 'Pascal triangle "column" sum', with quotes to suppress Google's automatic column:=row substitution, is disappointing.) But see (after) en.wikipedia.org/wiki/Binomial_coefficient#equation_8 $\endgroup$
    – Marc van Leeuwen
    Nov 18, 2013 at 6:40
  • $\begingroup$ @MarcvanLeeuwen: Thank you very much again. I fixed the typo. The $n \ge r$ is from that question in Ross. I referenced this source since it divulged that this identity = Fermat's Combinatorial Identity. Shame that these identities aren't more easily identifiable ! $\endgroup$
    – user53259
    Nov 18, 2013 at 7:09
0
$\begingroup$

Freestandingly, I dilate on why the OP is a duplicate of Combinatorics-number of permutations of $m$ A's and at most $n$ B's. Incidentally, please observe that all colours in this post are independent of any previous usage.

The OP here has the Fermat Combinatorial Identity: $ \sum_{\Large{r \le i \le n}} \dbinom{\color{blue}{i}}{\color{#FF4F00}{r}} = \dbinom{\color{brown}{n} + 1}{\color{green}{r + 1}}$

I'll denote with prime the variables in the Hockey Stick Identity that also occurs in the Fermat.

TMM has the Hockey Stick Identity : $\sum_{\Large{0 \le i' \le n'}} \dbinom{\color{blue}{m+i'}}{\color{#FF4F00}{i'}} = {\dbinom{\color{brown}{m + n'} + 1}{\color{green}{n'}}}.$

As already coloured, the changes of variable are :

$(1) \quad \color{blue}{i = m+i'} $
$(2) \quad \color{#FF4F00}{r = i'} $
$(3) \quad \color{brown}{n = m + n'} $
$(4) \quad \color{green}{r + 1 = n'} $

Verify the ranges of summation match: $r \le i \le n \iff \color{#FF4F00}{ i'} \le \color{blue}{m+i'} \le \color{brown}{m + n'} \iff \color{red}{i' - m} \le i' \le n'. $

But the $\color{red}{i' - m}$ is supposed to be $\color{red}{0}$.
Could someone please let me know of the discrepancy and error?

$\endgroup$
0
$\begingroup$

The left side is the most difficult to see. An easy way to see the equality is the following. Get arbitrarily r+1 elements from your n+1 set. This is 1 possible choice(that is, ${r \choose r}$ = ${r+1 \choose r+1 }$ = 1). Keep this elements. Now pick just one more (anyone) from your n+1-(r+1) that were left behind. Fix this new element in the $(r+1)^{th}$ position and then choose the others r from the initial r+1 that you had chosen in the first step. Repeating this process you will have all possible choices of r+1 elements from a set with n+1 elements, which is the right side of the equation. Try to do this with S={1,2,3,4,5} to see why ${5 \choose 3} = {2\choose 2} + {3\choose 2}+{4\choose 2}$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .