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. For example, if you know that events $A_1$ and $B_3$ happened, that is if the permutation contains $12$ and $43$, then you can replace $12$ with $1$ and $43$ with $3$, obtaining a permutation of $1$, $3$, $4$, ...,$n$, and each permutation of these $n-2$ numbers can be reconstructed to a permutation where $A_1$ and $B_3$ happen. 

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. Namely, let us colour the chosen $k$ elements black and the ones not chosen white, so that the numbers $1$,...,$n$ have $r$ clusters of consecutive black numbers and the rest is white. To enumerate those, let us first put $n-k$ placeholders for white numbers. Those placeholders define $n-k+1$ gaps (the one before the first one, the one between the first two, etc.). Choosing $i$ out of those $n-k+1$ gives us the locations of the $i$ black clusters. Now we need to fill those $i$ clusters with $k$ placeholders for white numbers putting at least one placeholder in each. This is the usual stars-and-bars: we have $\binom{k-1}{i-1}$ ways to do it. Thus, we get 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.