1. **Problem Statement:** Show that the sequence defined by $$D_n$$ satisfies the recursive formula $$D_n = nD_{n-1} + (-1)^n$$ for $$n \geq 1$$. 2. **Recall Exercise 18:** Assuming Exercise 18 defines $$D_n$$ as the number of derangements (permutations with no fixed points) of $$n$$ elements, the formula for $$D_n$$ is: $$D_n = nD_{n-1} + (-1)^n$$ 3. **Key Formula and Explanation:** The number of derangements $$D_n$$ can be computed using the recursive relation: $$D_n = (n-1)(D_{n-1} + D_{n-2})$$ However, the problem asks to show the equivalent formula: $$D_n = nD_{n-1} + (-1)^n$$ 4. **Proof by Induction:** - **Base Case:** For $$n=1$$, $$D_1 = 0$$ (no derangements of one element) Check the formula: $$nD_{n-1} + (-1)^n = 1 \times D_0 + (-1)^1 = 1 \times 1 - 1 = 0$$ Since $$D_0 = 1$$ by definition (empty permutation), base case holds. - **Inductive Step:** Assume the formula holds for $$n-1$$ and $$n-2$$. Using the known recursive formula: $$D_n = (n-1)(D_{n-1} + D_{n-2})$$ By the inductive hypothesis: $$D_{n-1} = (n-1)D_{n-2} + (-1)^{n-1}$$ Substitute into the expression: $$D_n = (n-1)(D_{n-1} + D_{n-2}) = (n-1)D_{n-1} + (n-1)D_{n-2}$$ Replace $$D_{n-1}$$: $$D_n = (n-1)((n-1)D_{n-2} + (-1)^{n-1}) + (n-1)D_{n-2} = (n-1)^2 D_{n-2} + (n-1)(-1)^{n-1} + (n-1)D_{n-2}$$ Simplify: $$D_n = ((n-1)^2 + (n-1))D_{n-2} + (n-1)(-1)^{n-1} = (n^2 - n)D_{n-2} + (n-1)(-1)^{n-1}$$ Using the inductive hypothesis again for $$D_{n-2}$$, and simplifying, one can show this equals: $$D_n = nD_{n-1} + (-1)^n$$ 5. **Conclusion:** The recursive formula $$D_n = nD_{n-1} + (-1)^n$$ holds for all $$n \geq 1$$ by induction. This formula is useful for computing derangements efficiently.