объясните пожалуйста почему ?
сумму всех натуральльных чисел от 1го до n можно вычислить как n * (n +1) / 2 . Например 5 1 + 2 + 3 + 4 + 5 = 15 или 5*6 /2 = 15
так вот почему это работает ? 5*6 /2 = 15 ?
Если подумать то сумма 1 + n будет такая же как и у 2 + n-1
Пример:
1 + 5 = 6
2 + 4 = 6
Но в этом ряде еще есть 3 что с ней. Давайте складывать столбиком так:
1 2 3 4 5
5 4 3 2 1
Каждый столбик равен 6 а столбиков 5 т.е. 5 * 6 = 30 как вижно тут 2 тройки а должна быть одна (и вообще всех чисел по 2), т.е мы должны разделить фигуру на 2 так:
Поэтому мы делим на 2 и это работает.
Линия просто отделяет дубликаты:
Построим треугольник из квадратов:
его площадь - равно итоговой сумме.
продублируем его:
развернём и соеденим их:
в итоге получаем:
площадь этого прямоугольника: n*(n+1), а т. к. мы использовали две фигуры, то площадь треугольника n*(n+1)/2
Похожим образом можно вывести формулу суммы квадратов, только там более сложные манипуляции в 3-х мерном пространстве.
s(n) = 1 + 2 + 3 + ... + (n-2) + (n-1) + n s(n) = n + (n-1) + (n-2) + ... + 3 + 2 + 1
Сложим попарно:
s(n) + s(n) = (1 + n) + (2 + (n-1)) + (3 + (n-2)) + ... ... + ((n-2) + 3) + ((n-1) + 2) + (n + 1) = = (1 + n) + (1 + n) + (1 + n) + ... + (1 + n) + (1 + n) + (1 + n) = = n * (1 + n)
s(n) = n * (n + 1) / 2
Докажем что sn = n(n + 1)/2 для любого целого неотрицательного n.
База индукции n = 0: s0 = 0(0 + 1)/2 = 0.
Индукционный шаг: пусть формула верна для sn-1. Вычислим sn:
sn = sn-1 + n = (n - 1)((n - 1) + 1)/2 + n = ((n - 1)n + 2n)/2 = (n - 1 + 2)n/2 = n(n + 1)/2.
Что и требовалось доказать.