Formula for the summation of this sequence?

Question

$$a(2n)=a(n)+a(n+1), a(2n+1)=2a(n+1),\mbox{ if }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. For instance, $S(5)$ should return $1+2+4+6+10$, etc.

Answer 1

Here is a explicit solution where the hardest part is finding the closest power of 2 to a number:

Under your definition, starting with $a(1)=1$ (though OEIS uses $a(0)=1$ and I would prefer $a(-1)=1$ for reasons which will become clear), you can use $$S(n)=\frac{19(n-2)^2+18(n-2)+44}{12}+e(n-2)$$
where $e(n-2)=0$ when $n-2$ is a power of two (i.e. $4,8,16,\ldots$). Use $n-1$ instead of $n-2$ for the OEIS partial sums (or $n$ instead of $n-2$ for my better starting point).

To find $e(m)$, look for the closest power of two to $m$, say $2^k$; halfway between two powers of two you can chose either. I think

if $m \ge 2^k$ then $e(m)=\dfrac{5(m -2^k)^2 -(2^{k+1}-6)(m -2^k)}{12}$

if $m \le 2^k$ then $e(m)=\dfrac{-7(m -2^k)^2 -(2^{k+1}+6)(m -2^k)}{12}$

and this does not work for the intital partial sums which are obviously $1$ and $3$.

To take your example of $S(5)$, this is $\frac{19\times 3^2+18\times 3+44}{12}+e(3)$ and $e(3)=\frac{5(3 -2)^2 -(4-6)(3 -2)}{12}$ or $\frac{-7(3 - 4)^2 -(8+6)(3 -4)}{12}$ in either case $\frac{7}{12}$, so $S(5)=\frac{269}{12}+\frac{7}{12}=23$ as you expected.

Answer 2

[I have moved my answer here since the duplicate thread is closed.]

First you should state in your question that your sequence starts from $a(0)$, and state the initial conditions and not just the recurrence relation, otherwise it is quite troublesome to figure out..

Let $b(n) = a(n) - a(n-1)$
$b(2n) = a(2n) - a(2n-1) = a(n+1) - a(n) = b(n+1)$
$b(2n+1) = a(2n+1) - a(2n) = a(n+1) - a(n) = b(n+1)$
Thus $ b(n) = \begin{cases} 4 & \text{if} & \exists i \in \mathbb{Z}^+ ( 2^i \leq n-2 < 3 \times 2^{i-1} ) \\ 2 & \text{if} & \exists i \in \mathbb{Z}^+ ( 3 \times 2^{i-1} \leq n-2 < 2^{i+1} ) \end{cases} $
(I do not consider $b(1)$, $b(2)$, $b(3)$ because they are simply boundary cases.)
So for any specified segment of the original sequence, its sum can be obtained easily by computing the first element and dealing with the differences for that segment one block (of either 4 or 2) at a time, because for each block the sum of the original sequence is an arithmetic progression. Since the blocks grow exponentially, the time complexity is logarithmic in the input.

Answer 3

According to the OEIS, the ordinary generating function for $a(n)$ is $$G(x) = \frac{1+x^2}{(1-x)^2} + \frac{2x^2}{(1-x)^2} \sum_{k=0}^\infty \left(x^{2^{k+1}}-x^{3 \cdot 2^k}\right)$$ The ordinary generating function for $s(n) = \sum\limits_{k=0}^n a(k)$ is then $\dfrac{G(x)}{1 - x}$.

I doubt that there is a "closed-form" formula for $a(n)$, in which case there won't be one for $s(n)$ either.