I need to somehow figure out what happens with the following sum:

$$\sum_{i=1}^{n^2 - 1} \frac{i^2}{[\frac{n^3}{3}]^2}$$

when $n \rightarrow \infty$.

Should it be zero? Should it be a constant?

If I try and guess that sum of squares from $1$ to $n$ is not more than $n^3%$, it follows that a sum of squares from $1$ to $n^2 - 1$ is not more than $n^6$ (am I right with that?), but that gives me the same asymptotic order in the numerator is the same as in the denominator.

So I am in doubt if this is the right upper bound, maybe it's really less than $n^6$, but I'm not sure.


Using the formula $$ \sum_{i=1}^{N} i^2 = \frac{N(N+1)(2N+1)}{6}, $$ your sum can be written as $$ \frac{1}{[\frac{n^3}{3}]^2} \sum_{i=1}^{n^2-1} i^2 = \frac{1}{[\frac{n^3}{3}]^2} \cdot \frac{(n^2-1)n^2(2n^2-1)}{6}. $$ It's not clear whether the denominator means $\frac{n^3}{3}$ or $\lfloor \frac{n^3}{3} \rfloor$ (these are the possibilities that come immediately to my mind). In either case1, for large $n$, the limit of the above function is the same as the limit $$ \lim_{n \to \infty} \left( \frac{3}{n^3} \right)^2 \cdot \frac{(n^2-1)n^2(2n^2-1)}{6}. $$ I presume you know how to evaluate this limit.

1EDIT: Here's the proof for the $\lfloor \frac{n^3}{3} \rfloor$ case. Our claim is essentially that as $x \to \infty$, the quantity $\frac{\lfloor x \rfloor}{x}$ approaches $1$. To see this, note that $$ \frac{x - 1}{x} \leq \frac{\lfloor x \rfloor}{x} \leq 1 $$ and apply the squeeze (sandwich) theorem.

  • $\begingroup$ Thank you so much! But could you please also explain why we can throw out the integer part for large $n$ and guarantee that the limits will be the same? It should be true if the limit of $\frac{x}{[x]}$ is 1 when $x \rightarrow \infty$, but the latter is not that obvious for me... $\endgroup$ – wh1t3cat1k Oct 17 '11 at 10:44
  • $\begingroup$ @wh1t3cat1k Added the proof for that claim. $\endgroup$ – Srivatsan Oct 17 '11 at 10:50
  • $\begingroup$ Thank you very much. This will surely help me. $\endgroup$ – wh1t3cat1k Oct 17 '11 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.