In combinatorics, the hockey-stick identity, Christmas stocking identity, boomerang identity, Fermat's identity or Chu's Theorem, states that if n ≥ r ≥ 0 {\displaystyle n\geq r\geq 0} are integers, then
( r r ) + ( r + 1 r ) + ( r + 2 r ) + ⋯ + ( n r ) = ( n + 1 r + 1 ) . {\displaystyle {\binom {r}{r}}+{\binom {r+1}{r}}+{\binom {r+2}{r}}+\cdots +{\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
∑ i = r n ( i r ) = ( n + 1 r + 1 ) for n , r ∈ N , n ≥ r {\displaystyle \sum _{i=r}^{n}{i \choose r}={n+1 \choose r+1}\qquad {\text{ for }}n,r\in \mathbb {N} ,\quad n\geq r}
or equivalently, the mirror-image by the substitution j → i − r {\displaystyle j\to i-r} , and by using the identify ( n k ) = ( n n − k ) {\displaystyle {n \choose k}={n \choose n-k}} :
∑ j = 0 n − r ( j + r r ) = ∑ j = 0 n − r ( j + r j ) = ( n + 1 n − r ) for n , r ∈ N , n ≥ r . {\displaystyle \sum _{j=0}^{n-r}{j+r \choose r}=\sum _{j=0}^{n-r}{j+r \choose j}={n+1 \choose n-r}\qquad {\text{ for }}n,r\in \mathbb {N} ,\quad n\geq r.}
Proofs
Inductive and algebraic proofs The inductive and algebraic proofs both make use of Pascal's identity:
( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) . {\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}.}
Inductive proof This identity can be proven by mathematical induction on n {\displaystyle n} . Base case Let n = r {\displaystyle n=r} ;
… excerpt ends here. Continue reading the full article.
