Recursive function proof using induction

Question

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?

Answer 1

$$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.

Answer 2

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.

Answer 3

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.