Derangements such that m < n 
For $n\in\Bbb N$, let $C_n$ denote the number of permutations of the set $\{1,2,\ldots,n\}$ in which $k$ is never followed immediately by $k+1$ for each $k=1,2,\ldots,n-1$.
  
  
*
  
*Find $C_n$.  
  
*Show that $C_n=D_n+D_{n-1}$ for each $n\in\Bbb N$.
  

How can part 2) be done?
Part 1) is simply 
$$\sum_{i=0}^{n-1} (-1)^i\binom{n-1}{i}(n-i)!$$

Recall that
$$D_n=n!\sum_{i=0}^n\frac{(-1)^i}{i!}\;.$$
Thus,
$$\begin{align*}
C_n&=\sum_{i=0}^{n-1}(-1)^i\binom{n-1}i(n-i)!\\
&=\sum_{i=0}^{n-1}(-1)^i\frac{(n-1)!}{i!}(n-i)\\
&=\sum_{i=0}^{n-1}(-1)^i\frac{n!}{i!}-\sum_{i=1}^{n-1}(-1)^i\frac{(n-1)!}{(i-1)!}\\
&=n!\sum_{i=0}^{n-1}\frac{(-1)^i}{i!}-(n-1)!\sum_{i=1}^{n-1}\frac{(-1)^i}{(i-1)!}\\
&=D_n-(-1)^n+(n-1)!\sum_{i=0}^{n-2}\frac{(-1)^i}{i!}\\
&=D_n-(-1)^n+D_{n-1}-(-1)^{n-1}\\
&=D_n+D_{n-1}\;.
\end{align*}$$
