Consider the sequence $$a_n = a_{n-1} a_{n-2} +n$$ for $n \geq 2$, with $a_0 = 1$ and $a_1 = 1$. Is $a_{2011}$ odd?
By writing all the terms of the sequence I see that $a_n$ is odd when $n$ is odd and greater than equal to $5$. But, I don't have any formal proof.
On
I may be presenting an argument which is not careful enough here, in which case, I hope community members correct me. However, I think this can be done by induction:
Statement: For $n \geq 4$, if $n$ is odd, then $a_{n}$ is odd; if $n$ is even, then $a_{n}$ is even.
Proof:
It is easy to show that $a_{4} = 14$, and $a_{5} = 75$.
Now suppose $n$ is odd. We wish to show $a_{n+1}$ is even. But this is easy, as $a_{n+1} = a_{n}a_{n-1} + n+1$. By the induction hypothesis, $a_{n}$ is odd and $a_{n-1}$ is even, and $n+1$ is even, so $a_{n+1}$ is even.
Now suppose $n$ is even. We wish to show $a_{n+1}$ is odd. But this is also easy, as $a_{n+1} = a_{n}a_{n-1} + n+1$. By the induction hypothesis, $a_{n}$ is even and $a_{n-1}$ is odd, and $n+1$ is odd, so $a_{n+1}$ is odd. So we're done.
On
Write $[x]$ for the residue class of $x$ modulo $2$. Then
$$ [a_n] = [a_{n-1}] [a_{n-2}] + [n] $$
Therefore
$$ [a_{2n}] = [a_{2n-1}][a_{2n-2}]+[2n] = [a_{2n-1}][a_{2n-2}] $$
We prove, by induction on $n$, that $[a_{2n}]=[0]$, for $n\ge2$. This is true for $n=2$, as $a_4=14$. If it's true for $n$, then
$$ [a_{2n+2}] = [a_{2n+1}][a_{2n}]=[0] $$
Turning to odd indices, we have, for $n\ge2$,
$$ [a_{2n+1}] = [a_{2n}][a_{2n-1}]+[2n+1] = [0][a_{2n-1}]+[2n]+[1] = [1] $$
because we already know that $[a_{2n}]=[0]$.
Thus all terms $a_{n}$ with even $n\ge4$ are even, while all terms $a_n$, with odd $n>4$ are odd.
HINT Use induction to prove that $a_n$ has the same parity as $n$ for $n \geq 4$.