Proof of combinatorics identity?

Prove the following identity.

Attachment image

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.

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

    • Commenter avatarLogin to reply the answers
Still have questions? Get your answers by asking now.