Growth rate of integer power sum

Click For Summary
SUMMARY

The discussion focuses on proving that the sum of integer powers, represented as \(\sum_{i=0}^n i^k\), is asymptotically equivalent to \(\Theta(n^{k+1})\). The limit formulation \(\lim_{n\to\infty}\frac{\sum_{i=0}^n i^k}{n^{k+1}}=CI\) is central to this proof. Participants suggest considering the integer sum as a lower sum approximation for the integral of the function \(f(x)=x^k\) to facilitate the proof.

PREREQUISITES
  • Understanding of asymptotic notation, specifically \(\Theta\) notation.
  • Familiarity with limits and their properties in calculus.
  • Knowledge of integral calculus, particularly the evaluation of integrals of polynomial functions.
  • Basic understanding of sequences and series in mathematical analysis.
NEXT STEPS
  • Study the properties of asymptotic notation, focusing on \(\Theta\) notation.
  • Learn about the relationship between sums and integrals, particularly in the context of Riemann sums.
  • Explore techniques for evaluating limits involving sums, such as the Squeeze Theorem.
  • Investigate polynomial growth rates and their implications in algorithm analysis.
USEFUL FOR

Mathematicians, computer scientists, and students studying algorithm analysis or mathematical analysis who are interested in understanding the growth rates of polynomial sums.

Thomas_
Messages
20
Reaction score
0
I need to show that

[tex]\sum_{i=0}^n i^k=\Theta(n^{k+1})[/tex]

Or equivalently

[tex]\lim_{n\to\infty}\frac{\sum_{i=0}^n i^k}{n^{k+1}}=C[/tex]I simply don't know what to do with the sum here. I know that I can rewrite or expand it, but that doesn't seem to help me. Any suggestions?

Thank you!
 
Physics news on Phys.org
You could think of the integer sum as a lower sum for an integral of f(x)=x^k.
 

Similar threads

Show that the limit (1+z/n)^n=e^z holds
  • · Replies 6 ·
Replies
6
Views
3K
On pointwise convergence of Fourier series
  • · Replies 3 ·
Replies
3
Views
2K
How should I show the following by using the signum function?
  • · Replies 14 ·
Replies
14
Views
2K
Compute sum (possibly using Parseval's formula)
  • · Replies 1 ·
Replies
1
Views
2K
Solution verification of ODE using Frobenius' method
  • · Replies 3 ·
Replies
3
Views
2K
Induction with binomial coefficient
  • · Replies 15 ·
Replies
15
Views
3K
Does this series converge uniformly?
  • · Replies 7 ·
Replies
7
Views
2K
Integrating Logarithmic Functions with Binomial Terms
  • · Replies 14 ·
Replies
14
Views
3K
Fourier series of this scale and shift of triangle wave
  • · Replies 1 ·
Replies
1
Views
2K
On the ratio test for power series
  • · Replies 2 ·
Replies
2
Views
2K