finding big omega of $n^k$ by splitting the sum (big-$O$ notation)

I'm currently trying to undestand one of the examples of my discrete mathematics book:

Show that: $1^k + 2^k + ··· + n^k = \Theta (n^{k+1})$

I have no trouble finding big - O, but rather finding the big - $\Omega $. Here's the solution of the book ( to find the lower bound of $1^k + 2^k + ··· + n^k$):

One way to get a sharper lower bound [...] is to first throw away approximately the first half of the terms, to obtain:

$1^k + 2^k + ·· ·+n^k ≥ ⌈(n + 1)/2⌉^k + ·· ·+(n − 1)^k + n^k$

$≥ ⌈(n + 1)/2⌉^k + ·· ·+⌈(n + 1)/2⌉^k + ⌈(n + 1)/2⌉^k$

$= ⌈n/2⌉⌈(n + 1)/2⌉^k ≥ (n/2)(n/2)^k = n^{k+1}/2^{k+1}$

for all n ≥ 1. We can now conclude that

$1^k + 2^k + ··· + n^k = \Theta(n^{k+1})$.

I do understand the definition of big $\Omega$. What I dont't understand is how the ceiling and/or floor function is used to find the lower bound. Here's my reasoning of the question:

• the sum $1^k + 2^k + ··· + n^k$ can be rewritten as (*) $$\sum_{i=1}^n i^k$$

• if we "split the sum", we get:

$$\sum_{i=1}^{n/2} 0+ \sum_{i={n/2+1}}^{n} i^k$$

• where the first term of the sum is a constant. We can the ingnore the first term and use the second to bound the initial sum (*) as follows:

$$\sum_{i=1}^n i^k ≥ \sum_{i={n/2+1}}^{n} i^k$$

• but the index must be an integer so,

$$\sum_{i=1}^n i^k ≥ \sum_{i={⌈n/2+1⌉}}^{n} i^k$$

It's here where I get stuck. I'm not sure how to use the ceilling function for the index and how to get then to $\Omega(n^{k+1})$. Can someone explain me how to procede properly?

Thanks!

Let's take $n$ to be even:

$\sum\limits_{i=1}^n i^k \ge \sum\limits_{i=\frac n2 +1}^n i^k \ge \sum\limits_{i=\frac n2 +1}^n \left(\frac n2\right)^k = \frac n2 \left(\frac n2\right)^k = \frac{n^{k+1}}{2^{k+1}}$

The case of $n$ odd is slightly more complicated, but there is so much space in the inequalities that this will work too. In particular for $k \ge 1$, the final term in the sum when $i=n$ is $n^k \ge \left(\frac n2\right)^k + \left(\frac n2\right)^k$ so

$\sum\limits_{i=1}^n i^k \ge \sum\limits_{i=\frac n2 +\frac12}^n i^k \ge \left(\frac n2\right)^k +\sum\limits_{i=\frac n2 +\frac12}^n \left(\frac n2\right)^k = \left(\frac n2+\frac12\right) \left(\frac n2\right)^k \ge \frac n2 \left(\frac n2\right)^k = \frac{n^{k+1}}{2^{k+1}}$

while for $k=0$ it is just $\sum\limits_{i=1}^n i^0 = n \ge \frac{n^1}{2^1}$.