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. Thanks.
This identity can be proven by induction on .
Base Case Let .
Inductive Step Suppose, for some , . Then .
It can also be proven algebraically with Pascal's Identity, . Note that
, which is equivalent to the desired result.
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 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 .