Is the 2011th term odd for this sequence and why so?

Question

$a_n = a_{n-1} \cdot a_{n-2} + n$, $n\ge2$, $a_0 = 1$ and $a_1 = 1$. Is $a_{2011}$ odd. Why so?

This is not a homework problem. I am appearing for an exam soon and I am solving sample questions for the exam. I don't know how to go ahead solving this.

So far I found out $a_2, a_3, a_4, a_5, a_6$ and $a_7$ but could not spot any pattern.

$a_{2011} = a_{2010} \cdot a_{2009} + 2011~$. So I am adding an odd number with the product, so whether or not the number is odd depends entirely on the product. This is as far as I could think.

Answer 1

$a_n\bmod 2$ depends only on $a_{n-1}\bmod 2$, $a_{n-2}\bmod 2$, and $n\bmod 2$. We can describe the transition $(n\bmod 2,a_{n}\bmod 2,a_{n-1}\bmod 2)\mapsto (n+1\bmod 2,a_{n+1}\bmod 2,a_{n}\bmod 2)$ by the following table $$\begin{matrix}(0,0,0)&\mapsto&(1,1,0)\\(0,0,1)&\mapsto&(1,0,0)\\ (0,1,0)&\mapsto&(1,0,1)\\ (0,1,1)&\mapsto&(1,0,1)\\ (1,0,0)&\mapsto&(0,0,0)\\ (1,0,1)&\mapsto&(0,1,0)\\ (1,1,0)&\mapsto&(0,1,1)\\ (1,1,1)&\mapsto&(0,1,1)\\\end{matrix} $$ and we start with $(1,1,1)$. The sequence will be eventually periodic and this allows you to predict the triple (and hence parity of $a_n$) belonging to $n=2011$.

Answer 2

The parity of $a_n$ does not depend on $a_{n-2}$ if $a_{n-1}$ is even. So if $a_{2n}$ is even, then $a_{2n+1}$ must be odd. Then $a_{2n+2}$ must be even. So the pattern is fixed as soon as you get $a_n$ even for an even $n$. But $a_4=22$, so for any odd $n>4$ we have $a_n$ odd. In particular $a_{2011}$ is odd.

Answer 3

Claim: for $n\ge 4$, $a_n $ is odd if n is odd and even if n is even.

We can verify directly $a_4$ is even as $a_2=a_0a_1+2=odd*odd+even=odd $ while $a_3=a_1*a_2+3=odd*odd+odd=even $ so $a_4=a_2*a_3+4=a_2*even +even =even $.

Assume $a_{n=2k} $ is even. Then $a_{n+1}=a_{n-1}*a_n+(n+1)=a_{n-1}*even+odd=odd $, and $a_{n+2}=a_n*a_{n+1}+(n+2)=even*odd+even=even $.

So, by induction we have shown our claim. So $a_{2011} $ is odd.

Answer 4

The sequence taken modulo $2$ is

$$1,1,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1\cdots$$

Now you have your pattern.

---

When there is an even factor in the product, the parity is that of $n$ and $a_{2011}$ is odd.