In
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
mathematics, the identity
:
or equivalently, the mirror-image by the substitution
:
:
is known as the hockey-stick, Christmas stocking identity, boomerang identity, or Chu's Theorem.
The name stems from the graphical representation of the identity on
Pascal's triangle
In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although o ...
: 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
A hockey stick is a piece of sports equipment used by the players in all the forms of hockey to move the ball or puck (as appropriate to the type of hockey) either to push, pull, hit, strike, flick, steer, launch or stop the ball/ puck during pla ...
,
Christmas stocking
A Christmas stocking is an empty sock or sock-shaped bag that is hung on Saint Nicholas Day or Christmas Eve so that Saint Nicholas (or the related figures of Santa Claus and Father Christmas) can fill it with small toys, candy, fruit, coins or ot ...
).
Proofs
Generating function proof
We have
:
Let
, and compare coefficients of
.
Inductive and algebraic proofs
The inductive and algebraic proofs both make use of
Pascal's identity:
:
Inductive proof
This identity can be proven by
mathematical induction
Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...
on
.
Base case
Let
;
:
Inductive step
Suppose, for some
,
:
Then
:
Algebraic proof
We use a
telescoping argument to simplify the computation of the sum:
:
Combinatorial proofs
Proof 1
Imagine that we are distributing
indistinguishable candies to
distinguishable children. By a direct application of
the stars and bars method, there are
:
ways to do this. Alternatively, we can first give
candies to the oldest child so that we are essentially giving
candies to
kids and again, with stars and bars and
double counting, we have
:
which simplifies to the desired result by taking
and
, and noticing that
:
:
Proof 2
We can form a committee of size
from a group of
people in
:
ways. Now we hand out the numbers
to
of the
people. We can divide this into
disjoint cases. In general, in case
,
, person
is on the committee and persons
are not on the committee. This can be done in
:
ways. Now we can sum the values of these
disjoint cases, getting
:
See also
*
Pascal's identity
*
Pascal's triangle
In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although o ...
*
Vandermonde's identity
In combinatorics, Vandermonde's identity (or Vandermonde's convolution) is the following identity for binomial coefficients:
:=\sum_^r
for any nonnegative integers ''r'', ''m'', ''n''. The identity is named after Alexandre-Théophile Vandermo ...
References
{{reflist
External links
On AOPSOn StackExchange, Mathematics''Pascal's Ladder'' on the Dyalog Chat Forum
Theorems in combinatorics
Mathematical identities
Articles containing proofs
Factorial and binomial topics