TITLE: A problem on recurrence relation
QUESTION [3 upvotes]: 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.

REPLY [0 votes]: 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.
{"set_name": "stack_exchange", "score": 3, "question_id": 388229}