1
$\begingroup$

I am looking to prove that for every fixed value of $k$, $ n^{k+1}= O(1^k + 2^k + \cdots + n^k) $

I have already proved that $1^k + 2^k +\cdots + n^k =O(n^{k+1})$ but I don't know how to make the jump to proving the opposite is true. I was thinking that induction might be the way to go (i.e. adding $(n+1)^k$ to each side and simplifying, but the way I did it didn't make anything obvious).

Any help will be very much appreciated.

Thanks, Nolan

  • 1
    Can you please define precisely $f=O(g)$? I think you are using a non-standard definition. The standard one says that $f=O(g)$ if the quotient $|f/g|$ is bounded from above by a constant.2012-09-24

2 Answers 2

1

$n\cdot n^k\geqslant\sum_{i=1}^ni^k\geqslant\sum_{i=1}^n\int_{i-1}^it^k\,\mathrm dt=\int_{0}^nt^k\,\mathrm dt=\frac{n^{k+1}}{k+1}.$ Hence, indeed $n^{k+1}=O(1^k+2^k+\cdots+n^k)$ when $n\to\infty$, and in fact, $ 1^k+2^k+\cdots+n^k=\Theta(n^k).$

  • 0
    The crucial step is that, for each $i$, $i^k\geqslant t^k$ for every $t$ in $[i-1,i]$ hence $i^k$ is at least the integral of $t^k$ on the interval $[i-1,i]$, divided by the length $1$ of the interval.2012-09-24
1

Lower bound without integrals: $\sum_{i=1}^n i^k \ge \sum_{i=\lfloor n/2 \rfloor }^n i^k \ge \frac{n-1}{ 2} \left( \frac{n-1}{ 2} \right)^k =\Omega(n^{k+1})$