Question 3
Let $S_n$ be the number of permutations $(a_1,a_2,\ldots,a_n)$ of $(1,2,\ldots,n)$ satisfying $1\le|a_k-k|\le2$ for every $k$. Prove that
$$\frac74S_{n-1}\lt S_n\lt 2S_{n-1}$$
for every integer $n\gt 6$.
$$\frac74S_{n-1}\lt S_n\lt 2S_{n-1}$$
for every integer $n\gt 6$.