3/2$\sum_{t=2}^{n} t *2_{}^{n-t}$

t is incremented by 2.

I am trying to find a exact formula for the sum of the series. If not, then would like to look for a tight upperbound on the sum.

This formula is derived from the series 1, 3, 8, 18, 39, 81, 166, 366, ..

The recurrence for the above series is T(n) = T(n-1)*2 + $\left \lceil{n/2}\right \rceil $

I got the summation formula by expanding this recurrence relation for the case when n is even.

Can anyone help me in solving the above summation or the recurrence relation.


The solution of the recurrence $$T(1)=1,\quad T(n)=2T(n-1)+\left \lceil{n/2}\right \rceil\quad\mbox{for $n>1$}$$ is $$T(n)=\frac{2^{n+4}-6n-15-(-1)^n}{12}.$$ We can easily verify that $T(1)=1$ and for $n>1$, $$T(n)-2T(n-1)=\frac{n}{2}+\frac{1-(-1)^n}{4}=\left \lceil{n/2}\right \rceil.$$ The first few terms are: 1, 3, 8, 18, 39, 81, 166, 336, 677, 1359.

  • $\begingroup$ Thanks. That looks correct. Can you explain how did you arrive to this result? $\endgroup$ – Gourav Kumar Jul 27 '17 at 9:13
  • $\begingroup$ Did you substitute $$\left \lceil{n/2}\right \rceil = \frac{n}{2}+\frac{1-(-1)^n}{4}$$ and then solved it using back substitution? or there is some better method ? $\endgroup$ – Gourav Kumar Jul 27 '17 at 9:17
  • $\begingroup$ @Gourav Kumar Yes, just with back substitution and then using the known formulas for geometric sums en.wikipedia.org/wiki/Geometric_series#Formula $\endgroup$ – Robert Z Jul 27 '17 at 9:28
  • $\begingroup$ I tried solving using back substituting, I am stuck at a point, where I get a arithmetic-geometric series, of the form $\sum_{t=1}^{n} t*2_{}^{n-t}.$ Can you suggest me how should I proceed from this point? or did I make any mistake? $\endgroup$ – Gourav Kumar Jul 27 '17 at 10:49
  • $\begingroup$ @GouravKumar Yes, $\sum_{t=1}^{n} t2^{n-t}=2^n\sum_{t=1}^{n} t2^{-t}$ and then use the fact that $\sum_{t=1}^{n} tx^t=xD(\sum_{t=1}^{n} x^t)$. $\endgroup$ – Robert Z Jul 27 '17 at 10:53

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.