Pascal's triangle identity?

Prove that nCn + (n+1)Cn+...+(n+x)Cn = (n+x+1)C(n+1)

1 Answer

Relevance
  • 6 months ago
    Favorite Answer

    The "trick" here is that C(n,n) = 1 for any n. (I prefer C(n,k) notation over nCk when typing, since there's no easy way to do subscripts.)

    So C(n,n) = 1 = C(n+1, n+1) lets you rewrite the sum as:

    C(n,n) + C(n+1,n) + C(n+2,n) + ... + C(n+x,n)

            = C(n+1,n+1) + C(n+1,n) + C(n+2,n) + ... + C(n+x,n)

    Those first two terms fit the defining Pascal's Triangle property: C(m,k) + C(m,k-1) = C(m+1,k) [0 < k <= m].  Replace those terms with C(n+2, n+1) then:

           = C(n+2, n+1) + C(n+2, n) + C(n+3, n) + ... + C(n+x, n)

    Again, the first two terms  match that basic identity, so rewrite the sum again and keep going:

          = C(n+3, n+1) + C(n+3, n) + ... + C(n+x, n)

          = C(n+4, n+1) + C(n+4, n) + ... + C(n+x, n)

          ... and so on, until

          = C(n+x, n+1) + C(n+x, n)

          = C(n+x+1, n+1)

Still have questions? Get your answers by asking now.