Сумма арифметической прогрессии?

Question

[adilet_murzaliev]

Подскажите пожалуйста, как вывели сокращения этой суммы:

Что-то никак не могу понять (привести), как получилось O(n^3). Или это просто допущение...

Answer 1

[Wataru]

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

Первый член - 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 таких пирамид можно сложить в параллелепипед.

Comments

[Alexandroppolus]

сумма 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.

для сумм k-й степени есть общий подход:
(i+1)^(k+1) - i^(k+1) = (k+1)*i^k + ...
если это просуммировать для i от 1 до n, то в левой части почти всё сократится. Ну и далее всё делим на (k+1) и выносим сумму i^k в одну сторону, всё остальное в другую, и получаем сумму i^k через суммы для всех предыдущих степеней

Answer 2

[Rsa97]

Внутренняя сумма раскладывается как 1 + 2 + 3 + ... + n - i = (1 + n - i) * (n - i) / 2