5
$\begingroup$

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.

1 Answers 1

4

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.

  • 0
    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...2011-10-17
  • 0
    @wh1t3cat1k Added the proof for that claim.2011-10-17
  • 0
    Thank you very much. This will surely help me.2011-10-17