Difference between revisions of "Combinatorial identity"
(→Proof) |
(→Examples) |
||
Line 39: | Line 39: | ||
== Examples == | == Examples == | ||
− | + | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=394407#394407 1986 AIME Problem 15] | |
− | * [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2000&p=385891 AIME | + | * [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2000&p=385891 2000 AIME II Problem 7] |
==See also== | ==See also== |
Revision as of 09:17, 10 March 2009
Hockey-Stick Identity
For .
This identity is known as the hockey-stick identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself are highlighted, a hockey-stick shape is revealed.
An image is supposed to go here. You can help us out by creating one and editing it in. Thanks.
Proof
Inductive Proof
This identity can be proven by induction on .
Base Case
Let .
.
Inductive Step
Suppose, for some ,
.
Then
.
Algebraic Proof
It can also be proven algebraically with Pascal's Identity, .
Note that
, which is equivalent to the desired result.
Combinatorial Proof
Imagine that we are distributing indistinguishable candies to
distinguishable children. By a direct application of Balls and Urns, 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 Balls and Urns,
, which simplifies to the desired result.
Vandermonde's Identity
Vandermonde's Identity states that , which can be proven combinatorially by noting that any combination of
objects from a group of
objects must have some
objects from group
and the remaining from group
.