Special permutations of $\{1,2,3,\ldots,n\}$ How do you show that number of permutations of $\{1,2,3,\ldots,n\}$ such that image of no two consecutive numbers is consecutive is
$$n! + \sum_{k = 1}^{n}(-1)^k\sum_{i = 1}^{k}\dbinom{k - 1}{i - 1}\dbinom{n - k}{i}2^i(n - k)!$$
In short we need to find number of permutations of $\{1,2,3,\ldots,n\}$ such that none of the following occur: $12, 23, \ldots, (n-1)n \quad $ and $ \quad21, 32, \ldots, n(n-1)$ that is no adjacent numbers should be consecutive.
I tried proving the formula but didn't get any satisfactory result, It seems to be inclusion exclusion principle would work, but there are too many cases to count. I tried to find a recurrence relation, but couldn't do it either. Afterwards I tried to get a generating function for the same but didn't succeed. I don't see any other approach to get through this but I think the most useful tool would be PIE however I'm not finding a good way to use PIE since number of cases are too much. Any help or hint would be highly appreciated. Thanks!
Note that:
I have read almost all the references related to the problem from OEIS.
I have read the whole paper https://projecteuclid.org/journals/annals-of-mathematical-statistics/volume-38/issue-4/Permutations-without-Rising-or-Falling-omega-Sequences/10.1214/aoms/1177698793.full   but in the paper there aren't any rigorous proofs and most of the proofs are just excluded simply by saying that 'use basic PIE to derive this'. I am looking for a more direct poof using enumerative combinatorics or generating functions.
I highly appreciate your time and efforts. Thanks.
 A: Here's a sign-reversing involution argument giving Flajolet's generating function. The argument and terminology are my own.
An "underlined permutation" is a permutation where each element is underlined, and consecutively increasing or consecutively decreasing adjacent subsequences may be underlined together. For instance, $\underline{3}\,\underline{1\,2}\,\underline{9\,10}\, \underline{8}\, \underline{7\,6\,5}\,\underline{4}$ is an underlined permutation.
There is a reasonably natural involution $\phi$ on the set of underlined permutations: take the rightmost adjacent increasing or decreasing pair and either break the underline between them or combine their underlines.
For example,
\begin{align*}
\phi(\underline{3}\,\underline{1\,2}\,\underline{9\,10}\, \underline{8}\, \underline{7\,6\,5}\,\underline{4})
&= \underline{3}\,\underline{1\,2}\,\underline{9\,10}\, \underline{8}\, \underline{7\,6\,5\,4} \\
\phi(\underline{3}\,\underline{1\,2}\,\underline{9\,10}\, \underline{8}\, \underline{7\,6\,5\,4})
&= \underline{3}\,\underline{1\,2}\,\underline{9\,10}\, \underline{8}\, \underline{7\,6\,5}\,\underline{4}
\end{align*}
Of course, if there are no adjacent increasing or decreasing pairs, we can do nothing, so define $\phi$ to be the identity in that "degenerate" case. In particular, you want to count the number of fixed points of $\phi$.
We may construct an underlined permutation in three steps: after writing $1\,2\,\ldots\,n$ in a line, (1) underline consecutive sublines together, (2) optionally reverse the order of individual sublines, and (3) permute the underlined groupings arbitrarily. For example, we might have

*

*$\underline{1\,2}\,\underline{3}\,\underline{4}\,\underline{5\,6\,7}\,\underline{8}\,\underline{9\,10}$

*$\underline{1\,2}\,\underline{3}\,\underline{4}\,\underline{7\,6\,5}\,\underline{8}\,\underline{9\,10}$

*$\underline{3}\,\underline{1\,2}\,\underline{9\,10}\, \underline{8}\, \underline{7\,6\,5}\,\underline{4}$
Define two statistics on an underlined permutation: the number $N$ of elements being permuted and the number $n$ of underlined groupings. The compositional formula for bivariate ordinary generating functions gives
$$\sum x^{N(\pi)} q^{n(\pi)} = \sum_{n=0}^\infty n! q^n (x+2x^2+2x^3+2x^4+\cdots)^n = \sum_{n=0}^\infty n! (qx)^n \frac{(1+x)^n}{(1-x)^n}\label{*}\tag{*}$$
where the sum is over all underlined permutations $\pi$.
Plug in $q=-1$ to $\eqref{*}$. The left-hand side becomes the generating function for the difference of the number of underlined permutations on $N$ elements with an even $n$ minus the number with odd $n$. Since $\phi$ preserves $N$ and, in the non-degenerate case, increments or decrements the number $n$ of underlined groupings by $1$, only degenerate $\pi'$ counted by A002464 contribute. Note that $N(\pi') = n(\pi')$ since every element must be underlined separately. Thus
$$\sum_{\pi'\text{ in }A002464} (-1)^{N(\pi')} x^{N(\pi')} = \sum_{n=0}^\infty n! (-x)^n \frac{(1+x)^n}{(1-x)^n}.\label{**}\tag{**}$$
Apply $x \mapsto -x$ to $\eqref{**}$ to get Flajolet's generating function:
$$\sum_{\pi'\text{ in }A002464} x^{N(\pi')} = \sum_{n=0}^\infty n! x^n \frac{(1-x)^n}{(1+x)^n}.$$

Edit: After writing this, I noticed Flajolet and Sedgewick discuss this generating function briefly and somewhat vaguely on p.373 of their text (which was mentioned on OEIS). They give a sketch of a sketch, but the ideas are similar.
Some routine but tedious calculations do allow you to extract the double sum formula above from this generating function. I probably don't have enough interest to type those manipulations out.
