how to find A tight bound to this function $\sum_{i=1}^n \sum_{j=1}^{n-i+1} j^2-1$?

Question

how to find A tight bound to this function $\sum_{i=1}^n \sum_{j=1}^{n-i+1} j^2-1$ ?

i tried the following : $\sum_{i=1}^n (2-i+1)/2 *((n-i+1)^2-1) <= \sum_{i=1}^n (2-i+1)^3/2 =n*(n^3+1)/2 = O(n^4) $ how can i found a better bound to this ?

Answer 1

Recall that

• $\sum_{k=1}^{n}k =\frac{n(n+1)}{2}$
• $\sum_{k=1}^n k^2=\frac{n(n+1)(2n+1)}{6}$
• $\sum_{k=1}^{n}k^3=\frac{n^2(n+1)^2}{4}$

then compute

$$\sum_{j=1}^{n-i+1} j^2-1=\sum_{j=1}^{n-i+1} j^2-\sum_{j=1}^{n-i+1}1$$

and finally

$$\sum_{i=1}^n \sum_{j=1}^{n-i+1} j^2-1$$

Answer 2

Almost as gimusi answered, consider $$S_n=\sum_{i=1}^n \sum_{j=1}^{n-i+1}(j^2-1)$$ Consider, for the time being $$\sum_{j=1}^{m}(j^2-1)=\sum_{j=1}^{m}j^2-\sum_{j=1}^{m}1=\frac{1}{6} m (m+1) (2 m+1)-m=\frac{1}{6} (m-1) m (2 m+5)$$ Now, replace $m$ by $(n-i+1)$ and group terms in $i$ to get $$\frac{1}{6} (m-1) m (2 m+5) =\frac{1}{6} \left(2 n^3+9 n^2+7 n\right)-i \left(n^2+3 n+\frac{7}{6}\right)+i^2 \left(n+\frac{3}{2}\right)-\frac{i^3}{3}$$ making $$S_n=\frac{1}{6} \left(2 n^3+9 n^2+7 n\right)\sum_{i=1}^{n}1-\left(n^2+3 n+\frac{7}{6}\right)\sum_{i=1}^{n}i+\left(n+\frac{3}{2}\right)\sum_{i=1}^{n}i^2-\frac 13\sum_{i=1}^{n}i^3 $$ and the summations are already given in gimusi's answer.

Just simplify and get a nice formula for $S_n$..