CZ-SK-MO 2003 Problem 3

A sequence $(x_n)_{n= 1}^{\infty}$ satisfies $x_1 = 1$ and for each $n > 1, x_n = \pm (n-1)x_{n-1} \pm (n-2)x_{n-2} \pm ... \pm 2x_2 \pm x_1$ . Prove that the signs " $\pm$ " can be chosen so that $x_n \ne 12$ holds only for finitely many $n$ .