2. Determine the number of permutations $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of the numbers $1,2, \ldots, n$ such that for every $k \in\{2,3, \ldots, n\}$, among the numbers $a_{1}, a_{2}, \ldots, a_{k-1}$ there is at least one that differs from $a_{k}$ by 1.
Solution. Let the number of considered permutations be $S_{n}$. We will prove by induction on $n$ that $S_{n}=2^{n-1}$. For $n=1$ and $n=2$, the statement is trivial. Assume that for the number $n$, $S_{n}=2^{n-1}$ holds. To find all permutations of the numbers $1,2, \ldots, n+1$ that have the desired property, we first prove that in every such permutation, the last number cannot be any of the numbers $2,3, \ldots, n$.

Consider an arbitrary permutation $(a_{1}, a_{2}, \ldots, a_{n+1})$ of the numbers $1,2, \ldots, n+1$ such that $a_{n+1} \neq 1$ and $a_{n+1} \neq n+1$. The number $a_{n+1}+1$ is located before the number $a_{n+1}$. According to the property of the permutation, it follows that $a_{n+1}+2$ is located before $a_{n+1}+1$, then $a_{n+1}+3$ is before $a_{n+1}+2$, and so on. Thus, the number $n+1$ is located before the number $n$, and moreover, it must be first. On the other hand, it is clear that the number $a_{n+1}-1$ is located before the number $a_{n+1}$. Now, from the property of the permutation, it follows that $a_{n+1}-2$ must be before $a_{n+1}-1$, then $a_{n+1}-3$ must be before $a_{n+1}-2$, and so on. Thus, the number 1 is before the number 2, and therefore 1 must be in the first position. This means that both 1 and $n+1$ must be in the first position, which is a contradiction.

From the above considerations, it follows that in the permutation, the last position must be occupied by the number 1 or the number $n+1$. If the last position is occupied by the number $n+1$, then the permutation $(a_{1}, a_{2}, \ldots, a_{n}, n+1)$ has the desired property if and only if the permutation $(a_{1}, a_{2}, \ldots, a_{n})$ of the numbers $1,2, \ldots, n$ has the desired property, and there are $2^{n-1}$ such permutations. If the number 1 is in the last position, then the permutation $(a_{1}, a_{2}, \ldots, a_{n}, 1)$ has the desired property if and only if the permutation $(a_{1}-1, a_{2}-1, \ldots, a_{n}-1)$ of the numbers $1,2, \ldots, n$ has the desired property, and there are $2^{n-1}$ such permutations. Finally, by the principle of addition, it follows that

$$
S_{n+1}=2^{n-1}+2^{n-1}=2^{n}
$$

which completes the proof.