Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

$$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.

share|cite|improve this question
If you knew it was in the OEIS, and if you knew the summation not to be in the OEIS, why didn't you say so, and save others the work? – Gerry Myerson Dec 26 '11 at 4:22
Gerry was rightly pointing out that asking about a sequence, knowing whether it's in OEIS but not mentioning that isn't mindful of others' time, since they will then probably waste time finding out and writing down what you already knew. – joriki Dec 26 '11 at 4:59
HSE: you are asking for help. It is usually best if you save other people's time when doing that. EVeryone will look into the OEIS when trying to find information about a sequence, even if one is really interested in the sums of the sequence and not the sequence itself (because the OEIS in its wisdom does give information about related sequences)... you did that, but did not tell anyone, thereby wasting everyone's time. – Mariano Suárez-Alvarez Dec 26 '11 at 5:11
We don't know that you looked in the OEIS, because you did not tell us you did. When asking a question, you should include as much information as you have which is relevant, because that helps others write better answers, avoid trying things you have already tried and possibly look in the correct direction. The information that the sequence you want is not in the OEIS is as relevant as pieces of information related to sequences of integers go. – Mariano Suárez-Alvarez Dec 26 '11 at 5:18
I would say that a good 75% of the questions asked here are asking for information which is somewhere. So no, this is not implied (as evinced by the comments above of a few of our most active users!) – Mariano Suárez-Alvarez Dec 26 '11 at 5:23

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.

share|cite|improve this answer
I believe my solution implies that there is a closed form for $a(n)$ using the floor function and base-2 logarithms but I am not interested in constructing it because it will not help the computation of the sum. – user21820 Dec 30 '11 at 6:49
@user21820: there is indeed a closed form. My answer can be tuned into a single line. – Henry Dec 31 '11 at 6:47
@Henry: I meant that the computation will still take logarithmic time so a closed form would not improve the time complexity, asymptotically anyway. =P – user21820 Dec 31 '11 at 7:58

[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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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