Answer to Question #254461 in Discrete Mathematics for Fiez

Question

(a) Prove that for all integer n à ¢ ‰ ¥ 3, P (n +1,3) - P(n,3) = 3P(n,2) b)Prove that n.P(n-1,n-1) = P(n,n) c)show that C(n+1,k) = C (n,k-1) + C(n,k)

Answer 1

(a)

$$P(n+1,3)=\dfrac{(n+1)!}{(n+1-3)!}=(n+1)(n)(n-1)$$

$$P(n,3)=\dfrac{(n)!}{(n-3)!}=n(n-1)(n-2)$$

$$P(n,2)=\dfrac{(n)!}{(n-2)!}=n(n-1)$$

Then for $n\geq3$

$$P(n+1,3)-P(n,3)$$

$$=(n+1)(n)(n-1)-n(n-1)(n-2)$$

$$=n(n-1)(n+1-n+2)$$

$$=3n(n-1)=3P(n,2)$$

(b)

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

$$P(n,n)=\dfrac{(n)!}{(n-n)!}=n!$$

Then

$$nP(n-1, n-1)=n(n-1)!=n!=P(n, n)$$

(c)

$$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)$$