# Summation of a recurrence relation? [duplicate]

Possible Duplicate:
Formula for the summation of this sequence?

$$a(2n)=a(n)+a(n+1)$$ $$a(2n+1)=2a(n+1)$$ $$n>1$$

Outputs $1, 2, 4, 6, 10, 12, 16, 20, 22$ etc, but I am trying to find a formula that finds the summation of these terms. In OEIS, this sequence is https://oeis.org/A005942

I can generate the terms fine but summing them up for large N takes forever. I'd like to find a way to handle this in O(lg n) time if there is a possible way to do it, mathematically speaking.

-

## marked as duplicate by Gerry Myerson, J. M., Ross Millikan, Zev ChonolesDec 30 '11 at 4:45

This question was marked as an exact duplicate of an existing question.

From $a(2n+1)=2a(n+1)$ and $a(2)=2$ it seems we should have $a(3)=4$ – Ross Millikan Dec 30 '11 at 0:46
@Ross Can you edit to add this and a tiny detail that the both recurrence holds only for $n>1$. Help would be appreciated. – user21436 Dec 30 '11 at 1:03
Didn't we just see this question a day or two ago? – Gerry Myerson Dec 30 '11 at 3:41
Then you edit it to bring it back to the front page - you don't just repeat it! Sheesh. – Gerry Myerson Dec 30 '11 at 3:53
@HSE: Is a few days too long to wait? Sometimes people who can answer the question are just not there at the moment. It should not be urgent at all, right... – user21820 Dec 30 '11 at 3:57

In particular, if you look at $2a(n) - 3(n-1)$, you should get something very similar to that OEIS sequence, perhaps with an offset. That should be enough to find the sum as the weighted sum or difference of two arithmentic progressions depending on whether the nearest power of 2 is above or below.
My answer was a reply to the original version of the partial sums of $1, 2, 3, 5, 6, 8, 10, 11, 12, 14, 16, 18, 20, 21, \dots$ – Henry Dec 30 '11 at 7:35