BALTIC-WAY 1996 Problem 7

A sequence of integers $a_{1}, a_{2}, \ldots$, is such that $a_{1}=1, a_{2}=2$ and for $n \geq 1$

$$a_{n+2}= \begin{cases}5 a_{n+1}-3 a_{n} & \text { if } a_{n} \cdot a_{n+1} \text { is even, } \\ a_{n+1}-a_{n} & \text { if } a_{n} \cdot a_{n+1} \text { is odd. }\end{cases}$$

Prove that $a_{n} \neq 0$ for all $n$.