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.
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
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.