1
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – David K Oct 26 '14 at 3:38

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.