# Thread: Mathematical Thinking: 2 Derangements/proof questions

1. ## Mathematical Thinking: 2 Derangements/proof questions

d(n) = (n − 1) (d(n − 1) + d(n − 2))

a) By considering d(n)−nd(n−1), use the formula above repeatedly to show that d(n)
satisfies the (first order) recurrence relation

d(n) = nd(n - 1) + (-1)^n, for n>=2

b) Use the previous part to show by induction that, for n >= 1, d(n) satisfies the explicit
equation

d(n) = n!(1-(1/1!)+(1/2!)-(1/3!)+(1/4!)-...+((-1)^n)/n!))

I was just about able to prove the formula at the top in a question before this (after a lot of help) which was very difficult, hopefully these 2 questions won't be as hard but i have no idea how to begin. Any help would be great

2. First, judging by the explicit formula for $\displaystyle d_n$, we have $\displaystyle d_1=0$ and $\displaystyle d_2=1$. (This information should have been given explicitly in the beginning of the problem.) Either from the explicit formula or from the recurrence equation one can calculate that $\displaystyle d_3=2$, $\displaystyle d_4=9$, etc. Therefore, $\displaystyle d_2=2d_1+1$ and $\displaystyle d_3=3d_2-1$, which fits the general law $\displaystyle d_n = nd_{n - 1} + (-1)^n$ that we have to show.

Next, from the original equation we get $\displaystyle d_n-nd_{n-1}=-(d_{n-1}+(n-1)d_{n-2})$. The right-hand side looks like the left-hand side where n has been replaced by n - 1. By continuing this way, we indeed can arrive at $\displaystyle d_n-nd_{n-1}=\pm(d_2-2d_1)=\pm 1$.

I think it is easier to prove $\displaystyle d_n-nd_{n-1}=(-1)^n$ by induction. Both the base case and the induction step have been shown above.

Proving the explicit formula by induction is also straightforward. Follow the general outline: identify the induction statement P(n); prove the base case P(1); fix an arbitrary n, assume P(n - 1) and use it to prove P(n). If you have difficulties, post what you have done and the description of the difficulty.