# How is this summation solved?

$$\sum_{i=\left\lceil\frac{n}{2}\right\rceil}^n \left\lceil\frac{n}{2}\right\rceil^k$$

This summation is a part of a proof (asymptotic lower bound) I was reading in my textbook, but I don't understand how they solved it. It doesn't look like any arithmetic or geometric series I have ever encountered, so how do you go about doing this? I just would like steps in the right direction or a very simple step by step.

The answer is $$\left(-\left\lceil\frac{n}{2}\right\rceil +n+1 \right)\left\lceil \frac{n}{2}\right\rceil^k\;.$$

Thank you very much.

The summation $\displaystyle\sum_{i = \lceil n/2\rceil}^{n}\left\lceil\dfrac{n}{2}\right\rceil^k$ is adding the constant $\left\lceil\dfrac{n}{2}\right\rceil^k$ exactly $n-\left\lceil\dfrac{n}{2}\right\rceil+1$ times.
Hence, the result is simply $\left(n-\left\lceil\dfrac{n}{2}\right\rceil+1\right)\left\lceil\dfrac{n}{2}\right\rceil^k$.
• If this is not clear enough, try evaluating the sum $\sum_{i=m}^n m^k.$ Then, since $\lceil n/2 \rceil \leq n,$ you can substitute $\lceil n/2 \rceil$ for $m$. – David K Oct 26 '14 at 3:38