aleem asked in Science & MathematicsMathematics · 4 months ago

# Proof of combinatorics identity?

Prove the following identity.

Relevance
• atsuo
Lv 6
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.

• 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.