Answer to Question #255838 in Discrete Mathematics for salaro

Question

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

Answer 1

$$C(n+1,k)=\dbinom{n+1}{k}=\dfrac{(n+1)!}{k!(n+1-k)!}$$

$$C(n,k-1)=\dbinom{n}{k-1}=\dfrac{n!}{(k-1)!(n-k+1)!}$$

$$C(n,k)=\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}$$

Then

$$C(n,k-1)+C(n,k)$$

$$=\dfrac{n!}{(k-1)!(n-k+1)!}+\dfrac{n!}{k!(n-k)!}$$

$$=\dfrac{n!(k+n-k+1)}{k!(n-k+1)!}=\dfrac{n!(n+1)}{k!(n-k+1)!}$$

$$=\dfrac{(n+1)!}{k!(n+1-k)!}=C(n+1,k)$$