# Prove Pascal's rule(n,k)+(n,k+1)=(n+1,k+1)

giorgiana1976 | College Teacher | (Level 3) Valedictorian

Posted on

We'll use combinatorial way to prove this identity.

We'll recall the factorial formula of combinations of n elements taken k at a time:

C(n,k) = n!/k!*(n-k)!

Now, we'll write the factorial formula of combinations of n elements taken k+1 at a time:

C(n,k+1) = n!/(k+1)!*(n-k-1)!

Now, we'll write the factorial formula of combinations of n+1 elements taken k+1 at a time:

C(n+1,k+1) = (n+1)!/(k+1)!*(n+1-k-1)!

We'll reduce like terms within brackets form denominator:

C(n+1,k+1) = (n+1)!/(k+1)!*(n-k)!

Now, we'll re-write the identity that has to be demonstrated:

n!/k!*(n-k)! + n!/(k+1)!*(n-k-1)! = (n+1)!/(k+1)!*(n-k)!

We'll create the same denominator at the fractions from the left side:

[n!*(k+1) + n!*(n-k)]//(k+1)!*(n-k)!

We'll remove the brackets from numerator:

(n!*k + n! + n!*n - n!*k)/(k+1)!*(n-k)!

We'll eliminate like terms within the brackets:

(n! + n!*n)/(k+1)!*(n-k)!

We'll factorize by n!:

n!*(n + 1)/(k+1)!*(n-k)!

But n!*(n + 1) = (n+1)!

The left side will become:

n!*(n + 1)/(k+1)!*(n-k)! = (n+1)!/(k+1)!*(n-k)!

We notice that the LHS = RHS, therefore the Pascal's rule is verified, so that n!/k!*(n-k)! + n!/(k+1)!*(n-k-1)! = (n+1)!/(k+1)!*(n-k)!.