How many permutations $\left(i_{1}, i_{2}, \ldots, i_{n}\right)$ of the numbers $1,2, \ldots, n$ are there such that for every $1 \leqq k \leqq n$,

$$
\left|i_{k}-k\right| \leqq 1
$$
1. Speaking intuitively, we only consider the permutations of the numbers $1,2, \ldots, n$ where each number either remains in its original position in the base order or takes the place of one of its neighbors. Thus, for the numbers $2,3, \ldots, n-1$, 3 positions come into play, while for the numbers 1 and $n$, only 2 positions are available.

Let $p_{n}$ denote the number of $n$-element permutations that satisfy (1). According to (1), the value of $i_{n}$ is either $n$ or $(n-1)$. In the first case, $\left(i_{1}, i_{2}, \ldots, i_{n-1}\right)$ is a permutation of the numbers $1,2, \ldots, n-1$ that also satisfies (1), so their number is $p_{n-1}$. In the second case, $n$ can only be equal to $i_{n-1}$, so $\left(i_{1}, i_{2}, \ldots, i_{n-2}\right)$ is a (1) permutation of the first $(n-2)$ natural numbers. The number of these is $p_{n-2}$, thus

$$
p_{n}=p_{n-1}+p_{n-2}
$$

Naturally, (2) only makes sense for $n>2$, so to determine the values of $p_{n}$, we need the first two values, which are clearly $p_{1}=1, p_{2}=2$. These initial values, together with (2), uniquely determine the value of $p_{n}$.

2. In the following, we seek an explicit expression for $p_{n}$.

In general, sequences that satisfy (2) are called Fibonacci-like sequences. From (2), the following three properties of Fibonacci-like sequences directly follow:

a) If the sequence $a_{n}$ is a Fibonacci-like sequence, then the sequence $c_{n}=\lambda a_{n}$, where $\lambda$ is any real number, is also of this type.

b) If the sequences $a_{n}, b_{n}$ are Fibonacci-like sequences, then the sequence $c_{n}=a_{n}+b_{n}$ is also of this type.

c) The geometric sequence $a_{n}=q^{n}$ is a Fibonacci-like sequence if and only if $q$ is a root of the equation

$$
q^{2}=q+1
$$

that is, if

$$
\text { either } \quad q_{1}=\frac{1+\sqrt{5}}{2}, \quad \text { or } \quad q_{2}=\frac{1-\sqrt{5}}{2} \text {. }
$$

It is sufficient, therefore, to find numbers $\alpha, \beta$ such that the sequence $c_{n}=\alpha q_{1}^{n}+\beta q_{2}^{n}$ has its first two terms equal to the first two terms of the above $p_{n}$ sequence, then for all $n$, $p_{n}=c_{n}$. Such a pair of numbers can be found from the system of equations:

$$
q_{1} \alpha+q_{2} \beta=p_{1}=1 \quad q_{1}^{2} \alpha+q_{2}^{2} \beta=p_{2}=2
$$

$$
\alpha=\frac{\sqrt{5}+1}{2 \sqrt{5}} \quad \text { or } \quad \frac{q_{1}}{\sqrt{5}}, \quad \beta=\frac{\sqrt{5}-1}{2 \sqrt{5}} \quad \text { or } -\frac{q_{2}}{\sqrt{5}}
$$

Therefore,

$$
p_{n}=\frac{1}{\sqrt{5}}\left(q_{1}^{n+1}-q_{2}^{n+1}\right)=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right\}
$$

This gives us the expression for $p_{n}$ in terms of the index $n$ alone. (It is easy to show that this expression yields a natural number for $p_{n}$ for any natural number $n$.)