Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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.

share|cite|improve this question

marked as duplicate by Gerry Myerson, J. M., Ross Millikan, Zev Chonoles Dec 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

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.

share|cite|improve this answer
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

Not the answer you're looking for? Browse other questions tagged or ask your own question.