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!
Best Answer
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}$.