The argument goes as follows. Let us consider the events $A_i=\{ i(i+1) \text{ occurs in a permutation} \}$ and $B_i=\{ (i+1)i \text{ occurs in a permutation} \}$. Some pairs of events like that cannot happen at the same time: $A_i$ is incompatible with both $B_i$ and $B_{i+1}$, and $B_i$ is incompatible with $A_{i+1}$. Note that if we choose specific $k$ compatible events among these, the number of permutations in which those events happen is equal to $(n-k)!$: you can collapse each $\{i,i+1\}$ onto $\{i\}$ without losing any information. According to inclusion-exclusion, the number of permutations where none of the events occur is thus equal to the sum
 $$
n!+\sum_{k=1}^n {(-1)^k}(n-k)! U_{n,k},
 $$ 
where $U_{n,k}$ is the number of possible choices of $k$ compatible events. 

Compatibility of events means that our $k$ chosen events are split into $i$ groups, where $1\le i\le k$, such that in each group the events are indexed by consecutive numbers and the same letter $A$ or $B$. This means that for a given $i$, the number of permutations is $2^i$ times the number of ways to choose $k$ elements of $n$ in such a way that there are exactly $i$ groups of consecutives in them (then the factor $2^i$ corresponds to the choice of $A$ or $B$ in each case). It remains to count the latter. That is done by the usual stars-and-bars counting, leading to the formula $$U_{n,k}=\sum_{i=1}^k 2^{i} \binom{k-1}{i-1}\binom{n-k+1}{i},$$ proving the requested result.