show that C(n+1,k)=C(n,k-1)+C(n,k)
Cn+1k=(n+1)!k!(n+1−k)!C_{n + 1}^k = \frac{{(n + 1)!}}{{k!(n + 1 - k)!}}Cn+1k=k!(n+1−k)!(n+1)!
Cnk−1+Cnk=n!(k−1)!(n−k+1)!+n!k!(n−k)!=n!kk!(n−k+1)!+n!(n−k+1)k!(n−k+1)!=n!k+n!(n−k+1)k!(n−k+1)!=n!(k+n−k+1)k!(n−k+1)!=n!(n+1)k!(n−k+1)!=(n+1)!k!(n+1−k)!C_n^{k - 1} + C_n^k = \frac{{n!}}{{(k - 1)!(n - k + 1)!}} + \frac{{n!}}{{k!(n - k)!}} = \frac{{n!k}}{{k!(n - k + 1)!}} + \frac{{n!(n - k + 1)}}{{k!(n - k + 1)!}} = \frac{{n!k + n!(n - k + 1)}}{{k!(n - k + 1)!}} = \frac{{n!(k + n - k + 1)}}{{k!(n - k + 1)!}} = \frac{{n!(n + 1)}}{{k!(n - k + 1)!}} = \frac{{(n + 1)!}}{{k!(n + 1 - k)!}}Cnk−1+Cnk=(k−1)!(n−k+1)!n!+k!(n−k)!n!=k!(n−k+1)!n!k+k!(n−k+1)!n!(n−k+1)=k!(n−k+1)!n!k+n!(n−k+1)=k!(n−k+1)!n!(k+n−k+1)=k!(n−k+1)!n!(n+1)=k!(n+1−k)!(n+1)!
(n+1)!k!(n+1−k)!=(n+1)!k!(n+1−k)!⇒Cn+1k=Cnk−1+Cnk\frac{{(n + 1)!}}{{k!(n + 1 - k)!}} = \frac{{(n + 1)!}}{{k!(n + 1 - k)!}} \Rightarrow C_{n + 1}^k = C_n^{k - 1} + C_n^kk!(n+1−k)!(n+1)!=k!(n+1−k)!(n+1)!⇒Cn+1k=Cnk−1+Cnk
Need a fast expert's response?
and get a quick answer at the best price
for any assignment or question with DETAILED EXPLANATIONS!
Comments