Problem 1178

Solution. By calculating the first few values, it can be conjectured that if $n>1$, then $a_{n}=(n-1)(n-3) \ldots$ (i.e., $a_{2 k}=(2 k-1)(2 k-3) \cdot 5 \cdot 3 \cdot 1$, and $\left.a_{2 k+1}=2 k(2 k-2) \ldots \cdot 6 \cdot 4 \cdot 2\right)$. We will prove that this is indeed the case by complete induction.
i) For $n=2,3,4$, this is obviously true, since $a_{2}=1, \quad a_{3}=2$, $a_{4}=\frac{2 \cdot 1+1!}{1}=3$

ii) Suppose the statement is true up to $n+2$; then $a_{n+2}=(n+1)(n-1) \ldots, a_{n+1}=n(n-2) \ldots$, and $a_{n}=(n-1)(n-3) \ldots$. Using these, we will prove the statement for $n+3$:

$$a_{n+3}=\frac{a_{n+2} a_{n+1}+n!}{a_{n}}$$

Notice that by the induction hypothesis,

$$\begin{aligned} a_{n+2} a_{n+1} & =((n+1)(n-1) \ldots) \cdot(n(n-2) \ldots)= \\ & =(n+1) n \cdot(n-1) \cdot(n-2) \cdot \ldots \cdot 4 \cdot 3 \cdot 2 \cdot 1=(n+1)! \end{aligned}$$

thus

$$\begin{aligned} a_{n+3} & =\frac{(n+1)!+n!}{a_{n}}=\frac{(n+1) n!+1 \cdot n!}{a_{n}}= \\ & =\frac{(n+2) n(n-1)(n-2)(n-3) \ldots 4 \cdot 3 \cdot 2 \cdot 1}{(n-1)(n-3) \ldots}= \\ & =(n+2) n(n-2)(n-4) \cdot \ldots \end{aligned}$$

Remark. We could have proved by complete induction that $a_{n+1}=\frac{n!}{a_{n}}$, from which it also easily follows that $a_{n}=(n-1)(n-3) \cdots$