# What is the asymptotic bound for $1n + 2(n-1) + 3(n-2) + … + (n-1)2 + n$?

My best guess is that the series $$\sum_{i=1}^n i(n-(i-1))$$ becomes $$2 \Bigg[ n + 2(n-1) + ... + \frac{n}{2} \bigg(n-\bigg(\frac{n}{2}-1\bigg)\Bigg)\Bigg]$$ So the highest term is $$n^2$$ and there are $$n$$ terms. Does that mean its $$O(n^3)$$? That seems high. Intuitively, it seems like it should be closer to $$O(n^2)$$ but I can't find a way to bring it down mathematically.

• Try distributing $i$ in the summation then break it out into multiple summations. Solve them each independently. – ryan Apr 17 '19 at 20:27
• Agh, that was it. $\sum_{i=1}^n in + \sum_{i=1}^n -(i^2)-i$ is roughly $\frac{1}{2}n^3 - \frac{1}{3}n^3$ so still $O(n^3)$ – Zaya Apr 17 '19 at 20:39
• Your proof sketch for $O(n^3)$ is perfectly fine -- nothing more needed! Of course, we'd like $\Theta$ and for that you need to do more. – Raphael Apr 17 '19 at 20:54

We can lower bound the sum roughly by $$\sum_{i=1}^n i(n+1-i) \geq \sum_{i=n/3}^{2n/3} (n/3)^2 \geq (n/3)^3.$$ This shows that it is $$\Omega(n^3)$$. Since each summand is at most $$n^2$$, the sum is also $$O(n^3)$$.
We can also compute the sum explicitly: $$\sum_{i=1}^n i(n+1-i) = (n+1) \sum_{i=1}^n i - \sum_{i=1}^n i^2 = (n+1) \frac{(n+1)n}{2} - \frac{n(n+1)(2n+1)}{6} = \frac{n(n+1)(n+2)}{6}.$$ This expression equals the binomial coefficient $$\binom{n+2}{3}$$, and we can prove this bijectively. The binomial coefficient counts triples $$(a,b,c)$$ of elements satisfying $$0 \leq a < b < c \leq n+1$$. Notice that $$1 \leq b \leq n$$, and this corresponds to summation over $$i$$. Given $$b$$, we have $$b$$ choices for $$a$$ and $$n+1-b$$ choices for $$c$$.
\begin{align*} T(n)&=1n + 2(n-1) + 3(n-2) + ... + (n-1)2 + n\\ &=n(1+2+...+n)-(1+2+3+...+n)\\ &=(n-1)(1+2+3+...+n)\\ &=\Theta(n^3) \end{align*}
From ryan's comment, the summation, when you distribute $$i$$ and split it into more summations comes to $$\sum_{i=1}^n i(n-(i-1)) = \sum_{i=1}^n (i*n) + \sum_{i=1}^n (-(i^2)-i)$$ which is roughly $$\frac{1}{2}n^3 - \frac{1}{3}n^3$$ so the asymptotic bound is, in fact $$O(n^3)$$
• Can you edit it so it's omega $n^3$ too? – lox Apr 17 '19 at 20:49