Permutations & Combinations
Derangement-like recurrence relation
MJAT_TS3_P1
Grade 12
Question:
Consider a function $f$ defined on the set of non-negative integers such that $f(0)=1$, $f(1)=0$, and $f(n)+f(n-1)=n\cdot f(n-1)+(n-1)\cdot f(n-2)$ for $n\geq 2$. Then $f(6)$ equals:
Step-by-Step Solution
Key Concept: Let $t_n = f(n) - n\cdot f(n-1)$. From the recurrence: $t_n = -t_{n-1}$, with $t_1 = f(1)-1\cdot f(0)=-1$. So $t_n=(-1)^n$. Then $\frac{f(n)}{n!} = \sum_{k=1}^n \frac{(-1)^k}{k!}+\frac{f(0)}{0!}$, which is the formula for derangements $D_n/n!$.
$f(n)=D_n=n!\sum_{k=0}^n(-1)^k/k!$. $f(6)=720\cdot(1-1+1/2-1/6+1/24-1/120+1/720)=265$.
Correct Answer: 265