Вопрос анализа алгоритмов из Руководства по разработке алгоритмов Скиены

Question

Я застрял на этом вопросе ... from Skiena's algorithm design manual.

This is part of the solution provided on his сайт-компаньон .

Мне неясно, почему добавление 1 необходимо для суммирования k = j к i + j. Я понимаю, что суммирование может быть далее разбито на суммирование от k = 1 до i + j за вычетом суммирования k = 1 до j, но я не понимаю, почему нужно добавить 1.

Answer 1

Пусть:

S - это сумма k от j до i + j .

Мы можем разбить это как вычитание суммы, т.е. s1 (из k = 1 до k = i + j) и s2 (от k = 1 до k = j-1).

s1 = i + j (суммирование от 1 до i + j)

s2 = j-1 (суммирование от 1 до j-1)

S = s1 - s2

S = (i + j ) - (j-1)

S = i + j - j + 1

Надеюсь, вы поняли ...