VMO 2003 Problem 3

Let $S_n$ be the number of permutations ($a_1$, $a_2$, ... , $a_n$) of (1, 2, ... , n) such that 1 ≤ $|a_k$ - k | ≤ 2 for all k. Show that (7/4) $S_{n-1}$ < $S_n$ < 2 $S_{n-1}$ for n > 6.