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.

This isn't a full answer, but might make a solution more tractable.
Define $S(n) = a(n+2) - a(n)$. (FYI I wasn't able to find $S(n)$ sequence in OEIS either)
Then, we get that 
$S(2n) = a(2n+2) - a(2n) = a(n+2) + a(n+1) + (n+1) - a(n+1) - a(n) - n = a(n+2) - a(n)  + 1 = S(n) + 1$
and
$S(2n+1) = a(2n+3) - a(2n+1) = a(n+1) + a(n) + 1 - a(n) - a(n-1) - 1 = a(n+1) - a(n-1) = S(n-1)$
So the recurrence for $S(2n) = S(n) + 1$ and $S(2n+1) = S(n-1)$. This still has a parity difference in the recursion, but is a bit simpler.
I spent a little while trying to work out a Josephus problem type solution for $S(n)$, with only partial results (i.e. if $n = 2^k + 3(2^j-1)$ with $0 \leq j < k$ and $2 \leq k$, then $S(n) = k - j + 4$). At the very least that shows that the differences between $a(n+2)$ and $a(n)$ vary between small constant values and up values around $\log n$.
