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.