Find the number of permutations of $1,2,\dots ,n$ that $1$ is in the first position and the difference between two adjacent numbers is $\le 2$ Find the number of permutations of $1,2,\dots ,n$ that $1$ is in the first and the difference between two adjacent numbers is $\le 2$
My attempt:It can be easily proved that by deleting $n$ we get the same question for $n-1$ numbers, so consider the answer of the question $f_n$.  In any case of $n-1$ numbers, we can at least put $n$ in one place that the condition is true again.  But in some cases we can put $n$ in two places. I mean the case that $n-1$ is in the end and $n-2$ is before that I can calculate these case.  Anyway, the answer in the book is:
$f_n=f_{n-1}+f_{n-3}+1$
 A: $\textbf{Hint:}$
Let $a_n$ be the number of permutations of $\{1,\cdots,n\}$ which satisfy this condition.
1) Show that the number of permutations starting with $\textbf{12}$ is given by $a_{n-1}$, 
since any such permutation can  ${\hspace .2 in}$be obtained by taking any valid
permutation of $\{1,\cdots,n-1\}$, adding 1 to each digit, and then placing a   ${\hspace .2 in} 1$ in front.
2) Show that the number of permutations starting with $\textbf{132}$ is given by $a_{n-3}\;$ (similarly to the last step).
3) Show that there is no permutation starting with $\textbf{134}\;$ (if $n>4$).
4) Show that there is only one permutation starting with $\textbf{135}\;$ (if $n>4$).
Therefore $a_n=a_{n-1}+a_{n-3}+1$.
A: I suppose your method is right, since I have calculated 
$$f_2=1$$
$$f_3=2$$
$$f_4=2+2=4$$
$$f_5=2+2+2=6$$
$$f_6=2+2+2+3=9$$
$$f_7=2+2+2+3+5=14$$
$$f_8=2+2+2+3+5+7=21$$
So it is clear from these calculations that the increasing part comes from the last increment, which stands for the numbers of that kind of permutations where $$2->3$$
With simple calculations this part is $$2*(n-5)+1=2n-9.$$

EDIT:
To make it clear, notice that $$\{3,4,...,n\}->\{2,4,...,n\},$$ so $$3->2$$ or $$n->2.$$
Case 1: $$n->2.$$ Then $$n-1->4$$$$3->5$$$$n-2->6$$$$4->7$$$$n-3->8$$$$5->9...$$ so only one possible answer.
Case 2: $$3->2. $$Then $$4->4.$$ $$\{5,...,n\}->\{5,...,n\}$$ and $$5->5$$ or $$5->6.$$ That is the same as $$\{1,...,n-4\}->\{1,...,n-4\}$$ and $$1->1$$ or $$1->2.$$ So by induction we get $$2*(n-5)$$ answers.
Altogether this part is $$2n-9.$$

so the total answer is $$f_n=2+2+2+3+5+7+...+(2n-9)=(n-3)(n-5)+6=n^2-8n+21$$
This holds for $$n>4$$
