The sum of an arithmetic progression?

Question

Mathematics

Please tell me how the reductions of this sum were deduced:

I can’t understand (give) something how it turned out to be O (n ^ 3). Or is it just an assumption...

Answer 1

The expression under the sum, marked in red in the picture, is the sum of an arithmetic progression, you yourself wrote it.
The first term is 1 (for j=i+1), the last one is ni (for j=n). There are ni in total. Well, then - the standard formula: the average of the extreme members, multiplied by their number.
How does this get O(n^3). According to the mind, it is necessary to open the brackets and decompose into the sum of three rows, depending on the degree of i in the term. Further, the sum of i will also give O(n^2). The sum over i^2 will give O(n^3). Here it is no longer possible to use an arithmetic progression, but this is a well-known formula - the sum of n squares will give n (n + 1) (2n + 1) / 6. It can be derived by taking the series f(x)=1+x+x^2+...+x^n = (1-x^{n+1})/(1-x) and finding (x* f'(x))'. Then you can substitute x=1 there. Or is there visual evidence. Each square is a square of cubes. All of them can be folded into a pyramid. 6 such pyramids can be folded into a parallelepiped.