6

Consider a function $f$ on non-negative integer such that $f(0)=1,f(1)=0$ and $f(n)+f(n-1)=nf(n-1)+(n-1)f(n-2)$ for $n \geq 2$. Show that $$\frac{f(n)}{n!}=\sum_{k=0}^n \frac{(-1)^k}{k!}$$

Here $$f(n)+f(n-1)=nf(n-1)+(n-1)f(n-2)$$ $$\implies f(n)=(n-1)(f(n-1)+f(n-2))$$ Then I am stuck.

Clive Newstead
  • 64,925
A.D
  • 6,400
  • 1
  • 20
  • 43
  • First, you prove this formula holds at $n=0,1$, and use induction. (assume this formula holds at $n=k-1,k-2$.) – Hanul Jeon Jan 24 '13 at 08:28

3 Answers3

5

Let $$ g(n) = \sum_{k=0}^n(-1)^k\frac{n!}{k!} \tag{1} $$ then \begin{align} g(n) &= \sum_{k=0}^n(-1)^k\frac{n!}{k!} \\ &= n\sum_{k=0}^{n-1}(-1)^k\frac{(n-1)!}{k!} + (-1)^n\frac{n!}{n!} \\ \\ \\ &= ng(n-1)+(-1)^n \\ \\ &= (n-1)g(n-1) +g(n-1)+(-1)^n \\ &= (n-1)g(n-1)+\Big((n-1)g(f-2)+(-1)^{n-1}\Big) + (-1)^n\\ &= (n-1)g(n-1) + (n-1)g(n-2) \end{align} so for any function $g$ that fulfills $(1)$ we have that $$ g(n)+g(n-1)=ng(n-1)+(n-1)g(n-2) $$ and with $g(0) = 1 = f(0)$, $g(1) = 0 = f(1)$ we conclude $g \equiv f$.

Cheers!

dtldarek
  • 37,381
3

$f(n)+f(n-1)=nf(n-1)+(n-1)f(n-2)\implies f(n)-nf(n-1)=-(f(n-1)-(n-1)f(n-2))$

Let $D(n)=f(n)-nf(n-1)$ then, previous relation becomes,

$D(n)=-D(n-1)=(-1)^2D(n-2)=\cdots=(-1)^{n-1}D(1)=(-1)^n$ (because $D(1)=f(1)-f(0)=-1$)

Thus, $$D(n)=(-1)^n\implies f(n)=nf(n-1)+(-1)^n=n!(\frac{f(n-1)}{(n-1)!}+\frac{(-1)^n}{n!})$$

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

Continuing in this fashion gives

$$f(n)=n!(\frac{1}{2!}-\frac{1}{3!}+\cdots+\frac{(-1)^n}{n!})$$

$\implies \frac{f(n)}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!}$

Hence, proved.

Aang
  • 14,672
3

$f(n)=(n-1)\{f(n-1)+f(n-2)\}$ for $n\geq 2$

Let for $n\in\mathbb N,~S_n:\frac{f(n)}{n!}=\sum_{k=0}^n \frac{(-1)^k}{k!}.$

It's a matter of simple verification that $S_0,~S_1$ are true.

Let $S_n$ be true $\forall~n\leq m~(\in\mathbb N).$ Then,

$\dfrac{f(m+1)}{(m+1)!}$

$=\dfrac{m\{f(m)+f(m-1)\}}{(m+1)!}$

$=\dfrac{m}{m+1}.\dfrac{f(m)}{m!}+\dfrac{1}{m+1}.\dfrac{f(m-1)}{(m-1)!}$

$=\dfrac{m}{m+1}\sum_{k=0}^m\dfrac{(-1)^k}{k!}+\dfrac{1}{m+1}\sum_{k=0}^{m-1}\dfrac{(-1)^k}{k!}$

$=\dfrac{m+1-1}{m+1}\sum_{k=0}^m\dfrac{(-1)^k}{k!}+\dfrac{1}{m+1}\sum_{k=0}^{m-1}\dfrac{(-1)^k}{k!}$

$=\sum_{k=0}^m\dfrac{(-1)^k}{k!}-\dfrac{1}{m+1}\{\sum_{k=0}^m\dfrac{(-1)^k}{k!}-\sum_{k=0}^{m-1}\dfrac{(-1)^k}{k!}\}$

$=\sum_{k=0}^m\dfrac{(-1)^k}{k!}-\dfrac{1}{m+1}.\dfrac{(-1)^m}{m!}$

$=\sum_{k=0}^m\dfrac{(-1)^k}{k!}+\dfrac{(-1)^{m+1}}{(m+1)!}$

$=\sum_{k=0}^{m+1}\dfrac{(-1)^k}{k!}$

$\implies S_{m+1}$ is true. Hence by the principle of mathematical induction the result follows.

Sugata Adhya
  • 3,979