IMO 1969 - Longlist Problems Question 31

(GDR 3) Find the number of permutations $a_1,\ldots,a_n$ of the set $\{1,2,\ldots,n\}$ such that $|a_i-a_{i+1}|\ne1$ for all $i=1,2,\ldots,n-1$. Find a recurrence formula and evaluate the number of such permutations for $n\le6$.