Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
Trending News
Help me with this, I don't understand how to get the answer-Combinatorics and sums?
I am basically trying to prove why
(n+r+1)C r = (n+r)Cr+...+nC0 = (n+r)Cn+...+ nCn
From another question asked on Yahoo answers some one said you can use the Christmas stocking theorem, how do you prove the Christmas stocking theorem or the hockey stick theorem?
(It is messy to write so if you want to know what this is about check http://mathworld.wolfram.com/ChristmasStockingTheo... )
By the way, the answer is supposed to be proven starting with Sum(nCn)=Sum(n+1Cn)=...= (n+r)C(r-1)+(n+r)Cr=(n+r+1)Cr
So, how do you go from each one being equal to the next and eventually getting the answer
1 Answer
- ♣ K-Dub ♣Lv 61 decade agoFavorite Answer
This identity is more commonly known as parallel summation.
Repeatedly use the identity aCb = (a-1)Cb + (a-1)C(b-1), until the lower index is zero.
Let me use the altermate notation C(a,b) instead.
C(n+r+1,r)
= C(n+r,r) + C(n+r,r-1)
= C(n+r,r) + C(n+r-1,r-1) + C(n+r-1,r-2)
.....
= C(n+r,r) + C(n+r-1,r-1) + C(n+r-2,r-2) + .... + C(n,0).
This equals
C(n+r,n) + C(n+r-1,n) + C(n+r-2,n) + ... + C(n,n)
when n is a nonnegative integer.
Hope this helps.
♣ ♣
