Problem 1034

Consider the characteristic polynomial for the recurrence $a_{n+2}-3 a_{n+1}+$ $2 a_{n}=0$, which is $x^{2}-3 x+2$. The roots are at 2 and 1 , so we know that numbers $a_{i}$ must be of the form $a_{i}=a 2^{i-1}+b$ for integers $a$ and $b$. Therefore $a_{2010}$ must equal to $a 2^{2009}+b$, where $a$ and $b$ are both integers. If the expression is always positive, it is sufficient to say $a_{1}$ is positive and $a$ is nonnegative, or $a+b>0$, and $a \geq 0$. For a given value of $a, 1-a \leq b \leq 2^{2012}-a 2^{2009}$, so there are $2^{2012}-a 2^{2009}+a$ possible values of $b$ for each $a$ (where the quantity is positive). $a$ can take any value between 0 and $2^{3}$, we sum over all such a in this range, to attain $9 \cdot 2^{2012}-(1+2+3+4+5+6+7+8) 2^{2009}+(1+2+3+4+5+6+7+8)$, or $36\left(2^{2009}\right)+36$, which is our answer.