How many possibilities exist to arrange ${1,....,n}$ so, that any number $k$ may only be placed, if $k-1$ or $k+1$ has already been placed? I'm doing some exercises in preparation for my exam in combinatorics and found the following task:

How many possibilities exist to arrange ${1,....,n}$ such that any number $k$ (apart from the first one to be placed) may only be placed, if $k-1$ or $k+1$ has already been placed? You can start with any number.

I tried some examples and found the following number of possibilities:
$1$ for $n=1$, $2$ for $n=2$, $4$ for $n=3$, namely: $(1,2,3),(2,3,1),(2,1,3),(3,2,1)$ and $10$ arrangements for $n=4$.
Obviously, $n!$ would be the maximum and if I start with $1$ or $n$, there is only one way to proceed with the arrangement.
Any help is appreciated.
 A: Let the first number placed be $i$. Then there are $i-1$ numbers less than $i$ and $n-i$ numbers greater than $i$ left to place. Numbers less than $i$ have to be placed in decreasing order, and numbers greater than $i$ have to be placed in increasing order.
Therefore the only thing we can change is at what spots we place numbers less than $i$, and which spots we place the numbers larger than $i$. This can be done in $\binom{n-1}{i-1}$ ways.
So in total there are
$$
\sum_{i=1}^{n}\binom{n-1}{i-1}=2^{n-1}
$$
ways to place the numbers.
A: Instead of choosing the permutation from left to right, choose it from right to left. For each of the rightmost $n-1$ spots, you must choose whether to place the highest unplaced number or the lowest unplaced number. There are $n-1$ of these two-way choices, so there are $2^{n-1}$ permutations. 
For example, when $n=4$, the last number is either $1$ or $4$. Say you choose $4$. Then the second to last number is either $1$ or $3$. Say you choose $1$. Then the third to last number is either $2$ or $3$. Whichever you choose forces the leftmost number to be the other. 
Your count of $10$ for $n=4$ is incorrect. Here are all $8$ valid permutations for $n=4$:
$$(4,3,2,1),(3,4,2,1),(3,2,4,1),(2,3,4,1),$$
$$(3,2,1,4),(2,3,1,4),(2,1,3,4),(1,2,3,4).$$
