Answer to Question #251145 in Discrete Mathematics for suhaa

Question

Prove that for all integer n3, P(n+1,3)−P(n,3)=3P(n,2).

Answer 1

We shall prove by mathematical induction.

For $n=3,$

$P(4,3)-P(3,3)=24-6=18=3(6)=3P(3,2)$

Thus it is true for $n=3$

Assume it is true for $n=k,k\geq3.$ Then

$P(k+1,3)-P(k,3)=3P(k,2)$

We shall show that it is true for $n=k+1,k\geq 3$

That is, P(k+2,3)-P(k+1,3)=3P(k+1,2)

$P(k+2,3)-P(k+1,3)=\frac{(k+2)!}{(k-1)!}-\frac{(k+1)!}{(k-2)!}=k(k+1)(k+2)-k(k-1)(k+1)\\ =3k(k+1)$

For the RHS

$3P(k+1,2)=3\left(\frac{(k+1)!}{(k-1)!}\right)=3k(k+1)$

Since LHS=RHS, then it is true for $n=k+1,k\geq 3$

Hence, $P(n+1,3)-P(n,3)=3P(n,2), n\geq 3$