Understanding the logic behind this summation The following is an excerpt from a proof that $\sum_1^n {i^k} = \theta(n^{k+1})$:
$$\sum_1^n{i^k} \ge \sum_{\lceil n/2 \rceil}^n{i^k} \ge \sum_{\lceil n/2 \rceil}^n{\lceil n/2\rceil^k}$$
The first clause in this inequality makes sense to me - but not the second. How can we say this without knowing that $i \ge \lceil n/2 \rceil$ (which we don't)? 
The proof goes on: 
$$\sum_{\lceil n/2 \rceil}^n{\lceil n/2\rceil^k} = (n-\lceil n/2 \rceil +1) * \lceil n/2\rceil^k$$
I also don't understand the result of this summation. To my logic,  $\displaystyle n-\lceil n/2 \rceil = \lfloor n/2 \rfloor$, and $\displaystyle \lfloor n/2 \rfloor + 1 = \lceil n/2 \rceil$ - which of course is the upper bound of our summation, but a) I feel like there's a reason for stating it this way that I don't (but need to) grasp; and b) $\lceil n/2 \rceil$ is just the upper bound of the summation - don't we have to include all the $i$ values from 1 to $\lceil n/2 \rceil$?
 A: But we do know that $\;i \geq \lceil n/2 \rceil\;$: $\;\sum_{\lceil n/2 \rceil}^n{i^k}\;$ is just shorthand for $\;\sum_{i = \lceil n/2 \rceil}^n{i^k}\;$, in other words the summation ranges over $\;\lceil n/2 \rceil \leq i \leq n\;$.

For the second part, you write that "$\;\lceil n/2 \rceil\;$ [...] of course is the upper bound of our summation".  But it isn't: it is the lower bound.
Explicitly writing the $\;i\;$ variable, the sum is $\;\sum_{i = \lceil n/2 \rceil}^n{\lceil n/2\rceil^k}\;$.  So we have to add $\;\lceil n/2\rceil^k\;$ for all $\;i\;$ in the range $\;\lceil n/2 \rceil \leq i \leq n\;$.
And since $\;\lceil n/2\rceil^k\;$ does not have any $\;i\;$ in it, this sum is equal to $\;\lceil n/2\rceil^k + \lceil n/2\rceil^k + \ldots\;$, repeated how many times?  Well, the number of $\;i\;$ in the range $\;\lceil n/2 \rceil \leq i \leq n\;$. And using $\;\text{upper bound} - \text{lower bound} + 1\;$, we see that this is $\;n - \lceil n/2 \rceil + 1\;$.
So the sum in the second part is $\;(n - \lceil n/2 \rceil + 1) \times \lceil n/2\rceil^k\;$.
A: And, of course,
the upper bound is easy:
$\sum_{i=1}^n{i^k}
\le \sum_{i=1}^n{n^k}
= n^{k+1}
$.
