Combinatorial Proof of $Q_n = D_n + D_{n-1}$

Question

Let $Q_n$ be the number of permutation of $n$ integers $\{1, 2, \cdots, n \}$ such that, in the permutation, every $i$ is not succeeded by $i+1$ and let $D_n$ be the number of derangement of $n$ integers. Find a combinatorial proof of $$Q_n = D_n + D_{n-1}.$$

For the algebraic proof it is easy. Just play with those factorials. But what about a combinatorial proof?

I tried the case where $n=4$ and I want to show for any permutation of the form $Q_4$, it is either in $D_4$ or $D_3$. But it is not true by simply looking at the permutation $1,4,3,2$ as there are already $2$ fixed points and now I am stuck.

Another thing that comes to my mind is that, for $n$ integers to permutation, at most $\lceil \frac{n}{2} \rceil$ of the integers can be fixed points, which is approximately half of the number of integer. Does this suggest that we should divide into two cases, one for those fixed points and another for non-fixed points?

Thanks in advance.

Answer 1

Sorry to post this as an answer, but I don't have enough reputation to do otherwise.

It seems like this question may have what OP is looking for.