1

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

Siminore
  • 35,136
usernolan
  • 69
  • 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. – Siminore Sep 24 '12 at 08:53

2 Answers2

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).$$

Did
  • 279,727
  • 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. – usernolan Sep 24 '12 at 09:02
  • 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. – Did Sep 24 '12 at 09:05
  • 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! – usernolan Sep 24 '12 at 09:06
  • 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. – Did Sep 24 '12 at 09:07
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})$$