[Discrete Math Recurrence Relations]

Consider the following recurrence relation:
D = (n − 1) (D + D ) , n ≥ 3,
n
D2 = 1,
n−1 n−2
 D 1 = 0 .
In this exercise we will produce a closed-form solution for this recurrence.
(a) Construct a new sequence fn by defining fn = Dn . Write a recurrence relation for fn by translating n! the recurrence for Dn.
(b) Define a new sequence gn as gn = fn − fn−1. Again, write the corresponding recurrence for gn, which should be a simple recurrence of the form
gn = h(n) · gn−1
for simple function h(n).
(c) Produce a solution for gn by plug-and-chug.
(d) Convert your solution to gn into a solution for fn and finally into one for Dn.
(e) Prove by induction that your solution satisfies the recurrence relation for Dn.