# 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, Ｊ. Ｍ., Ross Millikan, Zev ChonolesDec 30 '11 at 4:45

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.

-
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
-
I'm afraid I don't quite understand. Say I want to find the sum of the first seven terms, 1 + 2 + 4 + 6 + 10 + 12 + 16 = 51, I am assuming this would be some combination of lesser b summations? In this case, n=7, so we'd want b(3)? –  HSE Dec 30 '11 at 4:07
@HSE: First you might want to experiment with the sequence a bit. The difference operator $\Delta( n \rightarrow f(n) ) = ( n \rightarrow f(n)-f(n-1) )$ helps to reveal some patterns, and it can also be used to express and solve linear recurrence relations elegantly. After obtaining $b(2n) = b(2n+1) = b(n+1)$, it immediately implies that the differences can be divided into blocks where each succeeding block is the same as the preceding block with duplicated elements. Notice that $a(m+n) = a(m) + \sum_{i=1}^{n}{ b(m+i) }$. So if the whole block of differences are the same, can you find the sum? –  user21820 Dec 30 '11 at 6:36
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. –  Arkamis Sep 2 '12 at 1:59
This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. –  Sasha Sep 2 '12 at 3:33