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)!$

Hint. For the first part, apply the inclusion-exclusion formula. Note that the number of permutations such that $k + 1$ follows $k$ for each $k = k_1, k_2, \dots k_i$ is $(n-i)!$ irrespective of how the numbers $k_1, \dots, k_i$ are situated.
