0
$\begingroup$

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

  • 0
    Had to edit my post; figured out that I technically needed the summation, not a particular value2011-12-26
  • 3
    The sequence 1,2,4,6,10,12,... is in OEIS: http://oeis.org/search?q=1%2C2%2C4%2C6%2C10%2C12%2C16%2C20%2C22&language=english&go=Search. The sequence which you are looking for (the partial sums of the original sequence) is not in OEIS, however.2011-12-26
  • 1
    Have you tried computing the first few terms and then consulting the Online Encyclopedia of Integer Sequences?2011-12-26
  • 0
    I know it's in OEIS; but there's nothing for the summation of these terms2011-12-26
  • 7
    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?2011-12-26
  • 0
    Not sure I follow; I know the by-value sequence is in OEIS. The summation is not. I am asking about the summation.2011-12-26
  • 4
    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.2011-12-26
  • 1
    Again, not sure I follow. I'm not asking for the sequence in OEIS. I'm listing what the sequence is as well as its generating function. It's the exact same thing as listed in OEIS to begin with. I'm asking for the *summation* of terms, which is not listed in OEIS. I don't see how mentioning OEIS saves time.2011-12-26
  • 8
    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.2011-12-26
  • 0
    How is it wasting people's time by asking a question about something that ISN'T in OEIS? If it had been in OEIS I wouldn't have come here in the first place. I'm not trying to be rude here but the logic of the argument here does not make sense.2011-12-26
  • 7
    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.2011-12-26
  • 0
    I see where you're coming from, but I think it's something I'd normally consider "irrelevant" information. If someone is asking a question, it should be implied that it's because the information isn't already listed elsewhere. Otherwise, why ask? To me it feels like you're asking me to say "I have a question about X, and by the way, I couldn't find the answer to X anywhere else." Isn't that already implied?2011-12-26
  • 6
    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!)2011-12-26
  • 0
    As you can see, editing bumps questions back to the front page...2011-12-30
  • 0
    Good to know; thanks2011-12-30

3 Answers 3

5

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.

  • 0
    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.2011-12-30
  • 0
    @user21820: there is indeed a closed form. My answer can be tuned into a single line.2011-12-31
  • 0
    @Henry: I meant that the computation will still take logarithmic time so a closed form would not improve the time complexity, asymptotically anyway. =P2011-12-31
1

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

0

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.