aleem asked in Science & Mathematics Mathematics · 4 months ago

Proof of combinatorics identity?

Prove the following identity.

2 Answers

Relevance

atsuo
Lv 6
4 months ago
Favorite Answer
The left side of given equation is (x+n+1)Cn .

We know mCk = (m-1)Ck + (m-1)C(k-1) because
mCk
= m! / [(m-k)!k!]
= (m-1)!*m / [(m-k)!k!]
= (m-1)!*((m-k)+k) / [(m-k)!k!]
= (m-1)!*(m-k) / [(m-k)!k!] + (m-1)!*k / [(m-k)!k!]
= (m-1)! / [(m-k-1)!k!] + (m-1)! / [(m-k)!(k-1)!]
= (m-1)Ck + (m-1)C(k-1)

So
(x+n+1)Cn
= (x+n)Cn + (x+n)C(n-1)
= (x+n)Cn + (x+n-1)C(n-1) + (x+n-1)C(n-2)
= (x+n)Cn + (x+n-1)C(n-1) + (x+n-2)C(n-2) + (x+n-2)C(n-3)
・
・
・
= (x+n)Cn + (x+n-1)C(n-1) + (x+n-2)C(n-2) + (x+n-3)C(n-3) + ...
+ (x+1)C1 + (x+1)C0

And we know (x+1)C0 = (x+0)C0 = 1, so
(x+n+1)Cn
= (x+n)Cn + (x+n-1)C(n-1) + (x+n-2)C(n-2) + (x+n-3)C(n-3) + ...
+ (x+1)C1 + (x+0)C0
= [The sum from i=0 to n] (x+i)Ci
So given equation is proved.
- Login to reply the answers
Anonymous
4 months ago
The left side of given equation is (x+n+1)Cn .

We know mCk = (m-1)Ck + (m-1)C(k-1) because
mCk
= m! / [(m-k)!k!]
= (m-1)!*m / [(m-k)!k!]
= (m-1)!*((m-k)+k) / [(m-k)!k!]
= (m-1)!*(m-k) / [(m-k)!k!] + (m-1)!*k / [(m-k)!k!]
= (m-1)! / [(m-k-1)!k!] + (m-1)! / [(m-k)!(k-1)!]
= (m-1)Ck + (m-1)C(k-1)

So
(x+n+1)Cn
= (x+n)Cn + (x+n)C(n-1)
= (x+n)Cn + (x+n-1)C(n-1) + (x+n-1)C(n-2)
= (x+n)Cn + (x+n-1)C(n-1) + (x+n-2)C(n-2) + (x+n-2)C(n-3)
・
・
・
= (x+n)Cn + (x+n-1)C(n-1) + (x+n-2)C(n-2) + (x+n-3)C(n-3) + ...
+ (x+1)C1 + (x+1)C0

And we know (x+1)C0 = (x+0)C0 = 1, so
(x+n+1)Cn
= (x+n)Cn + (x+n-1)C(n-1) + (x+n-2)C(n-2) + (x+n-3)C(n-3) + ...
+ (x+1)C1 + (x+0)C0
= [The sum from i=0 to n] (x+i)Ci
So given equation is proved.
- Login to reply the answers

Still have questions? Get your answers by asking now.