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 has been asked before and already has an answer. If those answers do not fully address your question, please ask a new 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

1 Answer

Hint (as I don´t have time now to work it all out)

This is related to OEIS A053646 (distance to nearest power of 2) and various other sequences linked from there.

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.

It might be easier if you shifted all your terms and formulae down one.

-
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