5

I have a sequence as follows:

$$1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32 ...$$

What will be the closed form of the above sequence for the nth term?

I clearly see the pattern of $2^x$ getting repeated $2^{x-1}$ times. But I am getting confused in finding the closed form of this sequence.

EDIT:

Thanks @Arthur for providing the closed form. Now to extend the questiona bit further, what would be the sum upto nth term given the closed form?.

Looking at the closed form, it seems like that the sum would be of the order of $N^2$, but not able to find the exact value. I would like to see how much difference would it make because of the "ceiling" function.

user3243499
  • 369
  • 5
  • 16
  • 1
    I think you went wrong while writing the sequence here. Kindly reconsider it. – Abhinav Dhawan Sep 07 '17 at 12:43
  • Then $2=2^1$ should repeated $2^0=1$-times, not $2$-times. – Dietrich Burde Sep 07 '17 at 12:46
  • And 1 also does not follow the pattern you wrote. Have you wrote it incorrect by mistake or is this sequence correct? – Abhinav Dhawan Sep 07 '17 at 12:49
  • My bad. Sorry. Updated the sequence now. 2 should be repeated only once. – user3243499 Sep 07 '17 at 12:52
  • I do not understand very well to the notion of "closed-form". Can that be also a recursive expression? – TStancek Sep 07 '17 at 13:06
  • @TStancek Are you asking if the OP would accept a recursive expression as his solution? Or are you asking if "closed-form" is equivalent to "recursive"? I can answer the second one by saying a "closed-form" would be different from "recursive" in that a "closed-form" expression would not require calculating any of the previous entries in the sequence and instead directly find the desired term. – Brian J Sep 07 '17 at 17:56
  • @BrianJ Just wanted to know whether $a_0=1$ with $a_{2n}=2a_n$ for $n\neq 0$ and $a_{2n+1}=2a_n$ is also a closed form. – TStancek Sep 08 '17 at 07:24
  • @TStancek My understanding is that that would not be closed form, because to calculate when $a_{10}$, you'd need to calculate $a_5$, $a_4$, $a_2$, and $a_1$. – Brian J Sep 08 '17 at 12:06
  • http://oeis.org/search?q=1%2C2%2C4%2C4%2C8%2C8%2C8%2C8%2C16%2C16%2C16%2C16%2C16%2C16%2C16%2C16%2C32%2C32&language=english&go=Search leads immediately to a closed formula for your sequence. – Martin R Sep 12 '17 at 11:35

2 Answers2

25

If we start indexing at $n = 1$, we get $$a_n = 2^{\lceil \log_2 n\rceil}$$where $\lceil - \rceil$ is the ceiling function.

Arthur
  • 199,419
1

If we start indexing at $n=1$, the sum I believe is this:

$$s_n=(n-2^{\lfloor\log_2 n\rfloor})\cdot a_n+2\cdot\frac{4^{\lfloor\log_2 n\rfloor}-1}{3}+1$$

TStancek
  • 1,027
  • 5
  • 14