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?
 A: $$D_2=2(1-1+\frac 12)=1$$
We will use strong induction.
Let $n$ be such that
$$D_{n-1}=(n-1)!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}=(n-1)!S$$
and
$$D_n=n!\Bigl(\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}+\frac{(-1)^n}{n!}\Bigr)$$
$$=n!S+(-1)^n$$
then
$$D_{n+1}=n(D_{n-1}+D_n)$$
$$=n\Big((n-1)!S+n!S+(-1)^n)\Bigr)$$
$$=n.(n-1)!(n+1)S+n(-1)^n$$
$$=(n+1)!S+\color{red}{n(-1)^n}$$
Now observe that
$$(n+1)!\Bigl(\frac{(-1)^n}{n!}+\frac{(-1)^{n+1}}{(n+1)!}\Bigr)=$$
$$(n+1)(-1)^n-(-1)^n=\color{red}{n(-1)^n}$$
Done.
A: 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.
A: You made a mistake in your calculation. It should be
$$D_2 = 2! \sum_{k=0}^2 \frac{(-1)^k}{k!} = 2*(1-1+\frac{1}{2})=1$$ as expected.
