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

$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.

• Try some more terms; you haven't gone far enough. Also, note that you can work modulo 2: If $a_n$ is even, you can replace it with $0$, and if it's odd, you can replace it with a $1$. – Christopher Carl Heckman Apr 26 '16 at 6:27
• @ChristopherCarlHeckman Could you please explain the modulo 2 part a bit more elaborately? – Anibha Apr 26 '16 at 6:30
• If $a_{2n}$ is even, then $a_{2n+1}$ must be odd. Now what can you say about $a_{2n+2}$? – almagest Apr 26 '16 at 6:31
• @Anibha : If you want to determine whether $952\cdot 537$ is even or odd, you can replace $952$ with its remainder when you divide by $2$, and $537$ with its remainder when you divide by $2$. Thus, $952\cdot 537$ has the same parity as $0\cdot1=0$, so $952\cdot 537$ is even. – Christopher Carl Heckman Apr 26 '16 at 6:33

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.

• Very nicely and succinctly put! – fleablood Apr 26 '16 at 7:26

$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$.

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.

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$$

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