How to justify if the nth term of the sequence is even or odd?

Question

Consider the sequence $a_n$ = $a_{n-1} \cdot a_{n-2} + n$ for $n \geq 2$ with $a_0 = 1$ and $a_1 = 1$. Is $a_{2011}$ even or odd? Please justify.

Answer 1

HINT $\rm\ \ mod\ 2\::\ \ a_{n-2}\ \equiv\ n-2,\ \ a_{n-1}\ \equiv\ n-1\ \ \Rightarrow\ \ a_n\ \equiv\ n\:.\:$ Hence once the parity of $\rm\:a_n\:$ is the same as its index $\rm\:n\:$ for two successive indices, it remains so for all larger indices (by induction).

Answer 2

Hint: Suppose $n$ is even. The parities of $a_{n-1},a_{n-2}$ completely determine the parities of $a_{n+1},a_n$.