isi-entrance 2006 Q10

isi-entrance · India · solved Sequences and series, recurrence and convergence Closed-form expression derivation

Let $f(n)$ satisfy the recurrence $f(n) + f(n-1) = nf(n-1) + (n-1)f(n-2)$ with $f(0) = 1$, $f(1) = 0$. Find a closed form for $f(n)$.

$f(n) - nf(n-1) = (-1)(f(n-1) - (n-1)f(n-2)) = (-1)^2(f(n-2)-(n-2)f(n-3)) = \cdots = (-1)^{n-1}(f(1)-f(0)) = (-1)^n$.
So $\frac{f(n)}{n!} - \frac{f(n-1)}{(n-1)!} = \frac{(-1)^n}{n!}$.
Summing: $\frac{f(n)}{n!} - \frac{f(0)}{0!} = \sum_{k=1}^{n}\frac{(-1)^k}{k!}$.
$\Rightarrow \frac{f(n)}{n!} = \sum_{k=0}^{n}\frac{(-1)^k}{k!}$.
$\Rightarrow f(n) = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$.

Let $f(n)$ satisfy the recurrence $f(n) + f(n-1) = nf(n-1) + (n-1)f(n-2)$ with $f(0) = 1$, $f(1) = 0$. Find a closed form for $f(n)$.

Paper Questions

Q1 Q2 Q3 Q4 Q5 Q7 Q8 Q9 Q10