Question

Use the principle of induction to prove that the number of
derangements of n; dn; can be given by the recursion formula
d1 = 0; d2 = 1; dn = (n-1)(dn-1 + dn-2) (n >= 3).

Answer 1

use base case n =3 for induction basis

Answer 2

Assume n = k as you induction hypothesis.
Then, prove n = k+1