Answer to Question #257939 in Discrete Mathematics for allya

Question

show that C(n+1,k)=C(n,k-1)+C(n,k)

Answer 1

$C_{n + 1}^k = \frac{{(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)!}}$

$\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^k$