Question about a step in a derangement proof

Question

I read a proof about derangement and I didn't understand this step:

$d_n - nd_{n-1} = -(d_{n-1}-(n-1)d_{n-2}) \implies d_n=nd_{n-1}+(-1)^n$

---

I see that we have $S_n = -S_{n-1}$ if $S$ is the stuff on one side of the equation but I don't get what happened then. Where does $(-1)^n$ come from?

Answer 1

The second equation doesn't follow from just the first equation you wrote here. That equation has to be understood as a recurrence, and then it implies $S_n = (-1)^n K$ for some constant $K$ and $n$ in the range where the recurrence works.

Now you need an appropriate $K,$ which might be $S_m$ or $-S_m$ for integer $m.$

If $K = 1$ then you have $S_n = (-1)^n,$ which implies the second equation.

Answer 2

You could show this recurrence using the formula for the derangement numbers (proven using the principle of inclusion-exclusion): $$d_n = n!\sum^n_{i=0}\frac{(-1)^i}{i!}$$