# Fermat's Combinatorial Identity: How to prove combinatorially?

• Prove $\sum\limits_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity) [duplicate]

#### Solutions Collecting From Web of "Fermat's Combinatorial Identity: How to prove combinatorially?"

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 …

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}

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?

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