Use direct proof to show that Cn1 k Cn k1 Cnk by using the

Use direct proof to show that C(n+1, k) = C(n, k-1) + C(n,k) by using the definition of C(n, r)

Solution

Let\'s start with the right member of the equality :

(n1k1)+(n1k)=(n1)!((n1)(k1))!(k1)!+(n1)!((n1)k)!k!(n1k1)+(n1k)=(n1)!((n1)(k1))!(k1)!+(n1)!((n1)k)!k!

by definition

=(n1)!(nk)!(k1)!+(n1)!(n1k)!k!=(n1)!(nk)!(k1)!+(n1)!(n1k)!k!

simplifying (n1)(k1)=nk(n1)(k1)=nk

=(n1)!k(nk)!k!+(n1)!(nk)(nk)!k!=(n1)!k(nk)!k!+(n1)!(nk)(nk)!k!

since 1(n1k)!=nk(nk)(nk1)(nk2)...3211(n1k)!=nk(nk)(nk1)(nk2)...321

=(n1)!k+(n1)!(nk)(nk)!k!=(n1)!k+(n1)!(nk)(nk)!k!

=(n1)!(k+(nk))(nk)!k!=(n1)!(k+(nk))(nk)!k!

=(n1)!n(nk)!k!=(n1)!n(nk)!k!

=n!(nk)!k!=n!(nk)!k!

=(nk)=(nk)

by def