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).
It's the FIFA World Cup, not the Stanley Cup :D
ReplyDeleteTop 25 Best Pickleball Paddle Reviews 2019. Pickle ball is a fun game to indulge in no matter what your age is. If you are serious about the game, then upgrading your equipment can perhaps help you up your pickleball game. It killerspin ping pong table
ReplyDelete