<s>[INST] Recursive function proof using induction We get a $D_0, D_1, D_2, ...$ sequence, for the recursive function $D_n = (n-1)(D_{n-1} + D_{n-2})$ for every n ≥ 2, starting at $D_0 = 1, D_1 = 0$.
Using induction, prove that for every n≥0, $D_n = n! \sum_{k=0}^n = \frac{(-1)^k}{k!}$.
Now, taking for example n=2, the recursive function is $D_2 = (2-1)(D_{1} + D_{0}) = 1\cdot(0+1) = 1$.
Then, $D_2 = 2! \sum_{k=0}^2 = \frac{(-1)^k}{k!}$, and we get $2\cdot(1+(-1)+\frac{1}{2}) = 1$.
So how do we connect these two to prove what is requested?
 [/INST] We have
$$D_{n+1}=(n+1)!\sum_{k=0}^{n+1}\frac{-1^k}{k!}=(n+1)*n!*(\sum_{k=0}^{n}\frac{-1^k}{k!}+\frac{-1^{n+1}}{(n+1)!})=nD_n+n*n!\frac{-1^{n+1}}{(n+1)!}+n!(\sum_{k=0}^{n-1}\frac{-1^k}{k!}+\frac{-1^n}{n!}+\frac{-1^{n+1}}{(n+1)!})=nD_n+nD_{n-1}+n!(n\frac{-1^{n+1}}{(n+1)!}+\frac{-1^{n+1}}{(n+1)!}+\frac{-1^{n}}{(n)!})=n(D_n+D_{n-1})$$
This, together with $D_0=1=0!*\frac{-1^0}{0!}$ proves the induction.
</s>