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

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)!.