Question 74
For each integer $n \gt 1$, denote by $s_n$ the number of permutations $(a_1, a_2, ..., a_n)$ of $n$ first positive integers such that each permutation satisfies the condition:
$$
1 \le |a_k - k| \le 2 \quad \text{for every } k = 1, 2, ..., n.
$$
Prove that: $1.75 \cdot s_{n-1} \lt s_n \lt 2 \cdot s_{n-1}$ for all integers $n \gt 6$.
$$
1 \le |a_k - k| \le 2 \quad \text{for every } k = 1, 2, ..., n.
$$
Prove that: $1.75 \cdot s_{n-1} \lt s_n \lt 2 \cdot s_{n-1}$ for all integers $n \gt 6$.