6
$\begingroup$

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.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ I think you went wrong while writing the sequence here. Kindly reconsider it. $\endgroup$ – Abhinav Dhawan Sep 7 '17 at 12:43
  • $\begingroup$ Then $2=2^1$ should repeated $2^0=1$-times, not $2$-times. $\endgroup$ – Dietrich Burde Sep 7 '17 at 12:46
  • $\begingroup$ And 1 also does not follow the pattern you wrote. Have you wrote it incorrect by mistake or is this sequence correct? $\endgroup$ – Abhinav Dhawan Sep 7 '17 at 12:49
  • $\begingroup$ My bad. Sorry. Updated the sequence now. 2 should be repeated only once. $\endgroup$ – user3243499 Sep 7 '17 at 12:52
  • $\begingroup$ I do not understand very well to the notion of "closed-form". Can that be also a recursive expression? $\endgroup$ – TStancek Sep 7 '17 at 13:06
26
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks Arthur for your answer. Just curious to know, what would be the sum upto nth term of it. $\endgroup$ – user3243499 Sep 8 '17 at 19:14
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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