Сумма арифметической прогрессии?
Выражение под суммой, отмеченное красным на картинке - это сумма арифметической прогрессии, вы же сами написали. 

Первый член - 1 (при j=i+1), последний - n-i (при j=n). Всего их n-i. Ну а дальше - стандартная формула: среднее крайних членов, помноженное на их количество.

Как из этого получается O(n^3). По уму, надо раскрыть скобки и разложить на сумму трёх рядов, в зависимости от степени i в слагаемом. Дальше сумма i даст также O(n^2). Сумма по i^2 даст O(n^3). Тут уже нельзя арифметическую прогрессию применять, но это известная формула - сумма n квадратов даст n(n+1)(2n+1)/6. Ее можно вывести, если взять ряд f(x)=1+x+x^2+...+x^n = (1-x^{n+1})/(1-x) и найти (x*f'(x))'. Потом туда можно подставить x=1. Или есть визуальные доказательства. Каждый квадрат - это квадрат из кубиков. Их все можно сложить в пирамиду. 6 таких пирамид можно сложить в параллелепипед.
Внутренняя сумма раскладывается как 1 + 2 + 3 + ... + n - i = (1 + n - i) * (n - i) / 2