4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Christopher Carl Heckman Apr 26 '16 at 6:27
  • $\begingroup$ @ChristopherCarlHeckman Could you please explain the modulo 2 part a bit more elaborately? $\endgroup$ – Anibha Apr 26 '16 at 6:30
  • 2
    $\begingroup$ If $a_{2n}$ is even, then $a_{2n+1}$ must be odd. Now what can you say about $a_{2n+2}$? $\endgroup$ – almagest Apr 26 '16 at 6:31
  • 1
    $\begingroup$ @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. $\endgroup$ – Christopher Carl Heckman Apr 26 '16 at 6:33
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very nicely and succinctly put! $\endgroup$ – fleablood Apr 26 '16 at 7:26
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.