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
    This makes partial sense to me, but can you explain what the final integral means or implies? I'd like to understand this stuff, and I've been trying to make sense of it for quite a long time.2012-09-24
  • 0
    The integral of $t\mapsto t^k$ on $[0,n]$? Well, this is just the value at $n$ minus the value at $0$ of any primitive of $t^k$, for example $t^{k+1}/(k+1)$. The result is that your sum is between $n^{k+1}/(k+1)$ and $n^{k+1}$, hence the asymptotics you are after.2012-09-24
  • 0
    I've been looking at it further, and it makes more sense after the formatting edit and the n*n^k term at the beginning. Thanks so much for your help!2012-09-24
  • 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})$$