Help with a recurrence with even and odd terms I have the following recurrence that I've been pounding on:
$$
a(0)=1\\
a(1)=1\\
a(2)=2\\
a(2n)=a(n)+a(n+1)+n\ \ \ (\forall n>1)\\
a(2n+1)=a(n)+a(n-1)+1\ \ \ (\forall n\ge 1)
$$
I don't have much background in solving these things, so I've been googling around looking for different techniques. Unfortunately, I haven't been able to correctly apply them yet. So far I've tried:


*

*Characteristic equations

*Generating functions

*Plugging it into Wolfram Alpha

*Telescoping

*Observation


I'm sure that one or more of these is the way to go, but my biggest problem right now is figuring out how to deal with the idea that there are different equations for odd and even values of $n$. I'm not necessarily looking for a solution (though it would be gratefully accepted), but any nudges in the right direction would be much appreciated.

To follow up, it turned out that the speed problem described in my comment, below was related to the Decimal implementation in Python 2.7. Switching to Python 3.3 (and Java) made everything many orders of magnitude better.

If you consider each element and $a_0$, $a_1$, $a_2$,... You eventually see $a_2$ is just y(0)$a_{0}$.  And $a_3$ is just y(1)$a_{1}$.  $a_4$ = y(2)*y(0)$a_0$. $a_5$ = y(3)*y(1)$a_1$. Assuming you get a different answer for $a_0$ and $a_1$.  You will always get different results for even and odd inputs.
