Question about a step in a derangement proof 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?

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!}$$
