2
$\begingroup$

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.

  • 0
    From $a(2n+1)=2a(n+1)$ and $a(2)=2$ it seems we should have $a(3)=4$2011-12-30
  • 1
    @Ross Can you edit to add this and a tiny detail that the both recurrence holds only for $n>1$. Help would be appreciated.2011-12-30
  • 0
    Didn't we just see this question a day or two ago?2011-12-30
  • 0
    Yes; went unanswered unfortunately2011-12-30
  • 2
    Then you edit it to bring it back to the front page - you don't just repeat it! Sheesh.2011-12-30
  • 0
    Wasn't aware editing brought it to the front page; sorry!2011-12-30
  • 2
    @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...2011-12-30
  • 0
    The last question got taken over by a discussion of mentioning OEIS, which I felt detracted from the nature of the question itself.2011-12-30
  • 0
    @HSE: Ok see if you get my solution. I occasionally make typographical errors so please tell me if there are any.2011-12-30

1 Answers 1