# Find the Sum of the Series or a very close upper bound on Sum

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.

• Thanks. That looks correct. Can you explain how did you arrive to this result? – Gourav Kumar Jul 27 '17 at 9:13
• 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 ? – Gourav Kumar Jul 27 '17 at 9:17
• @Gourav Kumar Yes, just with back substitution and then using the known formulas for geometric sums en.wikipedia.org/wiki/Geometric_series#Formula – Robert Z Jul 27 '17 at 9:28
• 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? – Gourav Kumar Jul 27 '17 at 10:49
• @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)$. – Robert Z Jul 27 '17 at 10:53