# Pascal's triangle identity?

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

### 1 Answer

- husoskiLv 76 months agoFavorite 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)