Combinatorics question - count how many ways to write $1,2,...,n$ with a certain order A valid sequence is a sequence of length $n$ from the numbers $1,2,...,n$ such that:
1) every number appears once
2) apart from the first number in the sequence, every number $k$ has either a $k-1$ or a $k+1$ on its left (not necesarily adjacent).
For example:
the sequences $324156$ and $546321$ are valid. The sequence $435126$ is not (because there is no $2$ on the left side of $1$).
Show that the number of valid sequences of length $n$ is $2^{n-1}$
Would love if someone could give me a tip. Not the answer, just a direction. I tried solving it with recurrence relation and induction but it didn't work.
 A: Property 1) corresponds to the fact, that you are looking at permutations $\pi \in S_n$.
Property 2) yields that for any initial segment $\{\pi_1,\ldots,\pi_j\}$,  where $j \leq n$, there are some integers $a,b \in \{1,\ldots,n\}$, such that $\{\pi_1,\ldots,\pi_j\}=[a,b]\cap\mathbb{Z}$. Besides for every $j$, either $a$ decreases or $b$ increases.
Let us show that property by induction:
The base case is clear, as $\{\pi_1\}=[\pi_1,\pi_1]\cap\mathbb{Z}$. Now for $r \rightarrow r+1$ we have a few cases:
Let us first assume that $\pi_{r+1}=\pi_z+1$ for some $z \leq r$. We can use the induction hypothesis on $\{\pi_1,\ldots,\pi_r\}$ to get $\{\pi_1,\ldots,\pi_r\}=[a,b]\cap\mathbb{Z}$.
If $\pi_z$ isn't the maximal element of $\{\pi_1,\ldots,\pi_r\}$ then $a\leq \pi_z < b$ and thus $\pi_{r+1}=\pi_z+1 \in [a,b]\cap\mathbb{Z}$. Thus $\{\pi_1,\ldots,\pi_{r+1}\}=[a,b]\cap\mathbb{Z}$.
This is clearly a contradiction as now $r=|\{\pi_1,\ldots,\pi_r\}|=|[a,b]\cap\mathbb{Z}|=|\{\pi_1,\ldots,\pi_{r+1}\}|=r+1$.
Otherwise we have $\{\pi_1,\ldots,\pi_{r+1}\}=([a,\pi_z]\cap\mathbb{Z}) \cup(\{\pi_z+1\})=[a,\pi_z+1]\cap\mathbb{Z}$. Thus $b$ increases in this step.
The case $\pi_{r+1}=\pi_z-1$ for some $z \leq r$ is really similar. We will see that $a$ decreases in that step.
Now we know very well how those sequences look, in fact they are characterizied by the index set $J \subseteq \{2,\ldots,n\}$ that tells us if we want to decrease $a$ in that step [otherwise increase $b$] (this leaves only one possibility for $\pi_1$, you should be able to work this out).
