Number of permutations of thet set $\{1,2,...,n\}$ in which $k$ is never followed immediately by $k+1$ For $n \in \mathbb N$, let $C_n$ denote the number of permutations of the set $\{1,2,...,n\}$ in which k is never followed immediately by $k+1$ for each $k=1,2,...,n-1$
i) Find $C_n$
ii) Show that $C_n = D_n + D_{n-1}$ for each $n \in \mathbb N$
I know that the number of r-combinations of a set which contains no consecutive integers is given by $\binom{n-r+1}{r}$ but I'm not sure how to proceed from there.
Answer given for 
(i) $C_n = \sum_{i=0}^{n-1}(-1)^{i}\binom{n-1}{i}(n-i)!$

Hints:
1) Let $A_i$ be the set of permutations where $i$ is followed by $i+1$ for $1\le i\le n-1$, and then use the
 Inclusion-Exclusion formula to find $\left|A_1^{c}\cap\cdots\cap A_{n-1}^{c}\right|$.
2) Use that $\displaystyle(-1)^{i}\binom{n-1}{i}(n-i)!=(-1)^{i}\frac{(n-1)!}{i!}(n-i)=\left[(-1)^{i}\frac{n}{i!}-(-1)^{i-1}\frac{1}{(i-1)!}\right](n-1)!$
along with the formula for $D_n$.
