Originally Posted by

**malaygoel**

2. Given $\displaystyle f(n) + f(n-1) = nf(n-1) + (n-1)f(n-2)(\mbox{for}\ n\ge 2)$

and f(0)=1 and f(1) =0, prove that

$\displaystyle \frac{f(n)}{n!}=\sum^n_{k=0}\frac{(-1)^k}{k!}$

The solution to the difference equation initial value problem:

$\displaystyle f(n) + f(n-1) = nf(n-1) + (n-1)f(n-2)(\mbox{for}\ n\ge 2)$

$\displaystyle f(0)=1$ and $\displaystyle f(1) =0$

is unique, so we need only show that $\displaystyle f(n)$ defined by:

$\displaystyle \frac{f(n)}{n!}=\sum^n_{k=0}\frac{(-1)^k}{k!}\ \ \ (1)$

is a solution.

------------------------------------------------------------

Now suppose:

$\displaystyle f(n)=n!\ \sum^n_{k=0}\frac{(-1)^k}{k!}$,

which is just a rewrite of $\displaystyle (1)$, and $\displaystyle n \ge 2$.

Then:

$\displaystyle

f(n)=n (n-1)!\ \left[\sum^{n-1}_{k=0}\frac{(-1)^k}{k!}+\frac{(-1)^n}{n!}\right]

$

$\displaystyle

=n\ f(n-1)+ \frac{n(n-1)!(-1)^n}{n!}=n\ f(n-1)+(-1)^n

$

Hence also:

$\displaystyle

f(n-1)=(n-1)\ f(n-2)+(-1)^{n-1}

$

So:

$\displaystyle

f(n)+f(n-1)=nf(n-1)+(n-1)f(n-2)

$.

Also:

$\displaystyle

f(0)=0! (-1)^0/0!=1,\ \mbox{and}\ f(1)=1!((-1)^0/0!+(-1)^1/1!)=0

$,

That is we have shown that $\displaystyle f(n)$ defined by $\displaystyle (1)$ satisfies the initial value problem

and hence is the unique solution.

RonL