Формулы суммирования

Пусть, скажем, у нас есть алгоритм с циклом. Если переменная цикла принимает значение 5, то цикл выполняется 5 раз, а если значение равно 20, то двадцать. Вообще, если значение переменной цикла равно M, то цикл выполняется M раз. В целом если переменная цикла пробегает все значения от 1 до N, то суммарное число выполнений цикла равно сумме всех натуральных чисел от 1 до N. Мы записываем эту сумму в виде

N      конечное значение переменной суммирования
∑i
i=1    начальное значение переменной суммирования

Если какое-нибудь значение записано в виде подобной суммы, то его зачастую стоит упростить, чтобы результат можно было сравнивать с другими подобными выражениями. Не так уж просто сообразить, какое из двух чисел

N
∑(i2-i)
i=11

и

N
∑(i2-20i)
i=0

больше. Поэтому для упрощения суммы можно пользоваться следующими формулами, в которых C - не зависящая от i постоянная:

N      N
∑Ci = C∑i;
i=1    i=1

N    N-L
∑i = ∑(i+L);
i=L  i=0

N    N     L-1
∑i = ∑i  - ∑i;
i=L  i=0   i=0

N        N     N
∑(A+B) = ∑A  + ∑B;
i=1      i=1   i=1


N        N
∑(N-i) = ∑i;
i=0      i=0
Это равенство означает, что сумма чисел от 0 до N равна сумме чисел от N до 0.


При упрощении сумм можно сначала разбить их на более простые суммы с помощью вышеприведённых равенств, а затем заменять суммы с помощью остальных тождеств.

N
∑1 = N;
i=1

N
∑C = CN;
i=1


N
∑i = ( N(N+1) ) / 2;
i=1
Это равенство легко запомнить, если разбить числа от 1 до N на пары. Складывая 1 с N, 2 с N-1 и т.д., мы получим набор сумм, каждая из которых равна N+1. Сколько всего будет таких сумм? Разумеется их число равно половине числа разбиваемых на пары элементов, т.е. N/2. Поэтому сумма всех N чисел равна (N/2)*(N+1) = ( N(N+1) ) / 2.


N      N(N+1)(2N+1)      2N3+3N2+N
∑i2 = -------------- = -------------;
i=1         6                6      


N
∑2i = 2N+1 - 1;
i=0
Это равенство легко запомнить через двоичные числа. Сумма степеней двойки от нулевой до десятой равна двоичному числу 11111111111. Прибавив к этому числу 1, мы получим 100000000000, т.е. 211. Но этот результат на 1 больше суммы степеней двойки от нулевой до десятой, поэтому сама сумма равна 211 - 1. Если теперь вместо 10 подставить N, то мы придём к этому неравенству.


N      AN+1 - 1
∑Ai = ----------    для любого числа A;
i=1     A - 1

N
∑i2i = (N - 1)2N+1 + 2;
i=1

N
∑(1/i) ≈ ln(N);
i=1

N
∑log2(i) ≈ Nlog2(N) - 1,5.
i=1


Ярлыки: