Prove $Q_n=D_n+D_{n-1}$

Question

Use the identity $$(-1)^k\frac{n-k}{k!}=(-1)^k\frac{n}{k!}+(-1)^{k-1}\frac{1}{(k-1)!}$$ to prove that $Q_n=D_n+D_{n-1}$ Where $Q_n$ denotes the number of permutation's of the set {1,2,3 $\dots$ k} and $D_n$ denotes the number of dearrangements of the set {1,2,3 $\dots$ k}.
What I have done so far is from a preivous result noticed that $$Q_n=(n-1)!\sum_{k=0}^{n-1} (-1)^k\frac{n-k}{k!}$$ Thus from the identity we get; $$Q_n=n(n-1)!\sum_{k=0}^{n-1} (-1)^k\frac{1}{k!} + (n-1)!\sum_{k=0}^{n-1} (-1)^{k-1}\frac{1}{(k-1)!}$$ $$Q_n=n!\sum_{k=0}^{n-1} (-1)^k\frac{1}{k!}+ D_{n-1}$$ This is where I get stuck I need the term before $D_{n-1}$ to be $D_n$ however I need the sum to be going to n for that be true correct? Have I made a mistake so far, any help is appreciated.

Answer 1

Multiply the identity

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

by $(n-1)!$ and sum from $k=1$ to $k=n$; the righthand side yields

$$\begin{align*} (n-1)!\left(\sum_{k=1}^n(-1)^k\frac{n}{k!}+\sum_{k=1}^n(-1)^{k-1}\frac1{(k-1)!}\right)&=n!\sum_{k=1}^n\frac{(-1)^k}{k!}+(n-1)!\sum_{k=1}^n\frac{(-1)^{k-1}}{(k-1)!}\\ &=D_n-\frac{n!}{0!}+(n-1)!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}\\ &=D_n-n!+D_{n-1}\;, \end{align*}$$

and the lefthand side,

$$(n-1)!\sum_{k=1}^n(-1)^k\frac{n-k}{k!}=\sum_{k=1}^n(-1)^k\binom{n-1}k(n-k)!\;.$$

Thus,

$$\begin{align*} D_n+D_{n-1}&=n!+\sum_{k=1}^n(-1)^k\binom{n-1}k(n-k)!\\ &=\sum_{k=0}^{n-1}(-1)^k\binom{n-1}k(n-k)!\;. \end{align*}$$

For $k\in[n-1]$ let $A_k$ be the set of permutations of $[n]$ that have $k$ as a fixed point. Then

$$\left|\bigcap_{k\in I}A_k\right|=(n-|I|)!$$

whenever $\varnothing\ne I\subseteq[n-1]$, so by the inclusion-exclusion principle

$$\begin{align*} \left|\bigcup_{k\in[n-1]}A_k\right|&=\sum_{\varnothing\ne I\subseteq[n-1]}(-1)^{|I|+1}(n-|I|)!\\ &=\sum_{k=1}^{n-1}(-1)^{k+1}\binom{n-1}k(n-k)!\;. \end{align*}$$

This is the number of permutations of $[n]$ that fix at least one point of $[n-1]$, and there are $n!$ permutations of $[n]$ altogether, so $[n]$ has

$$\begin{align*} n!-\sum_{k=1}^{n-1}(-1)^{k+1}\binom{n-1}k(n-k)!&=n!+\sum_{k=1}^{n-1}(-1)^k\binom{n-1}k(n-k)!\\ &=\sum_{k=0}^{n-1}(-1)^k\binom{n-1}k(n-k)! \end{align*}$$

permutations that fix no point of $[n-1]$.

In other words, $D_n+D_{n-1}=Q_n$ if $Q_n$ is the number of permutations of $[n]$ that do not fix any $k\in[n-1]$; these are the permutations that either are derangements of $[n]$ or have $n$ as their unique fixed point. And when you express it that way, it’s completely obvious that $Q_n=D_n+D_{n-1}$.