## Task A-4.4.

A sequence is recursively defined as:

$$
\begin{gathered}
a_{1}=1, \quad a_{2}=3 \\
a_{n}=(n+1) a_{n-1}-n a_{n-2} \quad \text { for } n \geqslant 3
\end{gathered}
$$

Determine all natural numbers $n$ for which $a_{n}$ is divisible by 9.
## First Solution.

Using the given recursive relation, we obtain the equalities

$$
\begin{aligned}
& a_{3}=(3+1) a_{2}-3 a_{1}=9 \\
& a_{4}=(4+1) a_{3}-4 a_{2}=33 \\
& a_{5}=(5+1) a_{4}-5 a_{3}=153 \\
& a_{6}=(6+1) a_{5}-6 a_{4}=873
\end{aligned}
$$

Let's prove by induction that all terms $a_{n}$, for $n \geqslant 5$, are divisible by 9. For the base case, we see that $a_{5}=153=17 \cdot 9$, and $a_{6}=873=97 \cdot 9$.

Assume that for some $n \geqslant 5$, $9 \mid a_{n}$ and $9 \mid a_{n+1}$.

We need to show that the same holds for $a_{n+2}$. Using the induction hypothesis, from

$$
a_{n+2}=(n+3) a_{n+1}-(n+2) a_{n}
$$

we see that $a_{n+2}$ is the difference of two numbers divisible by 9, so it is also divisible by 9, thus proving the induction statement.

Considering the previously listed terms of the sequence, we conclude that the solution is $n=3$ and all $n \geqslant 5$.