Hockey-stick identity

Short description: Recurrence relations of binomial coefficients in Pascal's triangle

In combinatorial mathematics, the hockey-stick identity,^[1] Christmas stocking identity,^[2] boomerang identity, Fermat's identity or Chu's Theorem,^[3] states that if $n \geq r \geq 0$ are integers, then

(\binom{r}{r}) + (\binom{r + 1}{r}) + (\binom{r + 2}{r}) + \dots + (\binom{n}{r}) = (\binom{n + 1}{r + 1}) .

The name stems from the graphical representation of the identity on Pascal's triangle: when the addends represented in the summation and the sum itself are highlighted, the shape revealed is vaguely reminiscent of those objects (see hockey stick, Christmas stocking).

Formulations

Using sigma notation, the identity states

\sum_{i = r}^{n} (\binom{i}{r}) = (\binom{n + 1}{r + 1}) for n, r \in ℕ, n \geq r

or equivalently, the mirror-image by the substitution $j \to i - r$ :

\sum_{j = 0}^{n - r} (\binom{j + r}{r}) = \sum_{j = 0}^{n - r} (\binom{j + r}{j}) = (\binom{n + 1}{n - r}) for n, r \in ℕ, n \geq r .

Proofs

Generating function proof

Let $X = 1 + x$ . Then, by the partial sum formula for geometric series, we find that

X^{r} + X^{r + 1} + \dots + X^{n} = \frac{X^{r} - X^{n + 1}}{1 - X} = \frac{X^{n + 1} - X^{r}}{x}

.

Further, by the binomial theorem, we also find that

$X^{r + k} = (1 + x)^{r + k} = \sum_{i = 0}^{r + k} (\binom{r + k}{i}) x^{i}$ .

Note that this means the coefficient of $x^{r}$ in $X^{r + k}$ is given by $(\binom{r + k}{r})$ .

Thus, the coefficient of $x^{r}$ in the left hand side of our first equation can be obtained by summing over the coefficients of $x^{r}$ from each term, which gives

$\sum_{k = 0}^{n - r} (\binom{r + k}{r})$

Similarly, we find that the coefficient of $x^{r}$ on the right hand side is given by the coefficient of $x^{r + 1}$ in $X^{n + 1} - X^{r}$ , which is

$(\binom{n + 1}{r + 1}) - (\binom{r}{r + 1}) = (\binom{n + 1}{r + 1})$

Therefore, we can compare the coefficients of $x^{r}$ on each side of the equation to find that

$\sum_{k = 0}^{n - r} (\binom{r + k}{r}) = (\binom{n + 1}{r + 1})$

Inductive and algebraic proofs

The inductive and algebraic proofs both make use of Pascal's identity:

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) .

Inductive proof

This identity can be proven by mathematical induction on $n$ .

Base case Let $n = r$ ;

\sum_{i = r}^{n} (\binom{i}{r}) = \sum_{i = r}^{r} (\binom{i}{r}) = (\binom{r}{r}) = 1 = (\binom{r + 1}{r + 1}) = (\binom{n + 1}{r + 1}) .

Inductive step Suppose, for some $k \in ℕ, k ⩾ r$ ,

\sum_{i = r}^{k} (\binom{i}{r}) = (\binom{k + 1}{r + 1})

Then

\sum_{i = r}^{k + 1} (\binom{i}{r}) = (\sum_{i = r}^{k} (\binom{i}{r})) + (\binom{k + 1}{r}) = (\binom{k + 1}{r + 1}) + (\binom{k + 1}{r}) = (\binom{k + 2}{r + 1}) .

Algebraic proof

We use a telescoping argument to simplify the computation of the sum:

\begin{aligned} \sum_{t = 0}^{n} (\binom{t}{k}) = \sum_{t = k}^{n} (\binom{t}{k}) & = \sum_{t = k}^{n} [(\binom{t + 1}{k + 1}) - (\binom{t}{k + 1})] \\ = \sum_{t = k}^{n} (\binom{t + 1}{k + 1}) - \sum_{t = k}^{n} (\binom{t}{k + 1}) \\ = \sum_{t = k + 1}^{n + 1} (\binom{t}{k + 1}) - \sum_{t = k}^{n} (\binom{t}{k + 1}) \\ = (\binom{n + 1}{k + 1}) - \underset{0}{\underset{⏟}{(\binom{k}{k + 1})}} & by telescoping \\ = (\binom{n + 1}{k + 1}) . \end{aligned}

Combinatorial proofs

Proof 1

Imagine that we are distributing $n$ indistinguishable candies to $k$ distinguishable children. By a direct application of the stars and bars method, there are

(\binom{n + k - 1}{k - 1})

ways to do this. Alternatively, we can first give $0 ⩽ i ⩽ n$ candies to the oldest child so that we are essentially giving $n - i$ candies to $k - 1$ kids and again, with stars and bars and double counting, we have

(\binom{n + k - 1}{k - 1}) = \sum_{i = 0}^{n} (\binom{n + k - 2 - i}{k - 2}),

which simplifies to the desired result by taking $n^{'} = n + k - 2$ and $r = k - 2$ , and noticing that $n^{'} - n = k - 2 = r$ :

(\binom{n^{'} + 1}{r + 1}) = \sum_{i = 0}^{n} (\binom{n^{'} - i}{r}) = \sum_{i = r}^{n^{'}} (\binom{i}{r}) .

Proof 2

We can form a committee of size $k + 1$ from a group of $n + 1$ people in

(\binom{n + 1}{k + 1})

ways. Now we hand out the numbers $1, 2, 3, \dots, n - k + 1$ to $n - k + 1$ of the $n + 1$ people. We can then divide our committee-forming process into $n - k + 1$ exhaustive and disjoint cases based on the committee member with the lowest number, $x$ . Note that there are only $k$ people without numbers, meaning we must choose at least one person with a number in order to form a committee of $k + 1$ people. In general, in case $x$ , person $x$ is on the committee and persons $1, 2, 3, \dots, x - 1$ are not on the committee. The rest of the committee can then be chosen in

(\binom{n - x + 1}{k})

ways. Now we can sum the values of these $n - k + 1$ disjoint cases, and using double counting, we obtain

(\binom{n + 1}{k + 1}) = (\binom{n}{k}) + (\binom{n - 1}{k}) + (\binom{n - 2}{k}) + \dots + (\binom{k + 1}{k}) + (\binom{k}{k}) .

References

↑ CH Jones (1996) Generalized Hockey Stick Identities and N-Dimensional Block Walking. Fibonacci Quarterly 34(3), 280-288.
↑ W., Weisstein, Eric. "Christmas Stocking Theorem" (in en). http://mathworld.wolfram.com/ChristmasStockingTheorem.html.
↑ Merris, Russell (2003). Combinatorics (2nd ed.). Hoboken, N.J.: Wiley-Interscience. pp. 45. ISBN 0-471-45849-X. OCLC 53121765. https://www.worldcat.org/oclc/53121765.

External links

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Hockey-stick identity. Read more

[1] CH Jones (1996) Generalized Hockey Stick Identities and N-Dimensional Block Walking. Fibonacci Quarterly 34(3), 280-288.

[2] W., Weisstein, Eric. "Christmas Stocking Theorem" (in en). http://mathworld.wolfram.com/ChristmasStockingTheorem.html.

[3] Merris, Russell (2003). Combinatorics (2nd ed.). Hoboken, N.J.: Wiley-Interscience. pp. 45. ISBN 0-471-45849-X. OCLC 53121765. https://www.worldcat.org/oclc/53121765.

[1]

[2]

[3]

Anonymous

Search

Hockey-stick identity

Namespaces

More

Page actions

Contents

Formulations

Proofs

Generating function proof

Inductive and algebraic proofs

Inductive proof

Algebraic proof

Combinatorial proofs

Proof 1

Proof 2

See also

References

External links

Navigation

Navigation

Help

googletranslator

Navigation

Wiki tools

Wiki tools

Anonymous

Search

Hockey-stick identity

Formulations

Proofs

Generating function proof

Inductive and algebraic proofs

Inductive proof

Algebraic proof

Combinatorial proofs

Proof 1

Proof 2

See also

References

External links

Navigation

Wiki tools

Page tools

Other projects

Categories