Monday, June 12, 2006

Hockey! Topic: Probability & Combinatorics. Level: AMC/AIME.

Theorem: (Hockey Stick) $ rCr+(r+1)Cr+\cdots+nCr = (n+1)C(r+1) $.

Proof: Consider the number of ways to choose $ r+1 $ people out of a group of $ n+1 $ people. This is clearly $ (n+1)C(r+1) $. Now try counting this another way. Suppose we number the people $ 1, 2, \ldots, n+1 $. Consider the cases based on the highest-numbered person.

If the highest-numbered person in the $ r+1 $ person group is $ \le r $, we clearly cannot have $ r+1 $ people.

On the other hand, if the highest-numbered person, numbered $ k+1 $, is greater than $ r $, we automatically include $ k+1 $ and choose the remaining $ r $ people from the lower $ k $ numbers, giving $ kCr $. So we thus have

$ (n+1)C(r+1) = rCr+(r+1)Cr+\cdots+nCr $

as desired. QED.

--------------------

Comment: This always struck me as one of the most interesting theorems, partially because of its name, which is derived from the shape it forms on Pascal's Triangle (try finding each of the terms).

1 comment:

  1. It's the FIFA World Cup, not the Stanley Cup :D

    ReplyDelete