## Task 3 - 271243

How many different words $\left(a_{1} a_{2} a_{3} \ldots a_{n-1} a_{n}\right)$ can be formed in total from the letters $a_{i} \in$ $\{1,2,3,4,5\}, i=1, \ldots, n$ such that

$$
\left|a_{j}-a_{j+1}\right|=1
$$

for $j=1, \ldots, n-1$?
Let $A_{i, n}$ be the number of words, consisting of $n$ letters, that end with $a_{i}$. The desired number is then $A_{n}:=A_{1, n}+A_{2, n}+A_{3, n}+A_{4, n}+A_{5, n}$.

Obviously, the recursion holds:

$$
A_{i, n+1}= \begin{cases}A_{2, n} & \text { if } i=1 \\ A_{i-1, n}+A_{i+1, n} & \text { if } 2 \leq i \leq 4 \\ A_{4, n} & \text { if } i=5\end{cases}
$$

Thus, we have

$$
\begin{aligned}
A_{n+1} & =\left(A_{2, n}\right)+\left(A_{1, n}+A_{3, n}\right)+\left(A_{2, n}+A_{4, n}\right)+\left(A_{3, n}+A_{5, n}\right)+\left(A_{4, n}\right) \\
& =A_{n}+A_{2, n}+A_{3, n}+A_{4, n}
\end{aligned}
$$

Furthermore,

$$
\begin{aligned}
A_{n+2} & =A_{n+1}+A_{2, n+1}+A_{3, n+1}+A_{4, n+1} \\
& =\left(A_{n}+A_{2, n}+A_{3, n}+A_{4, n}\right)+\left(A_{1, n}+A_{3, n}\right)+\left(A_{2, n}+A_{4, n}\right)+\left(A_{3, n}+A_{5, n}\right) \\
& =3 A_{n}-A_{1, n}+A_{3, n}-A_{5, n}
\end{aligned}
$$

Finally, we have

$$
\begin{aligned}
A_{n+3} & =3 A_{n+1}-A_{1, n+1}+A_{3, n+1}-A_{5, n+1} \\
& =3 A_{n+1}-A_{2, n}+\left(A_{2, n}+A_{4, n}\right)-A_{4, n} \\
& =3 A_{n+1}
\end{aligned}
$$

By explicit calculation, we also find that $A_{1}=5, A_{2}=8, A_{3}=14$. In total, we then have

$$
A_{n}= \begin{cases}5 & \text { if } n=1 \\ 8 \cdot 3^{m-1} & \text { if } n=2 m \\ 14 \cdot 3^{m-1} & \text { if } n=2 m+1, n \neq 1\end{cases}
$$