Немного алгоритмов recurence relation 0 + 1 + 2 + 3.....+ n-1 + n = (n(n+1))/2
почему мы получаем (n(n+1))/2 ?
Спасибо.

Предыдущий
вопрос Следующий
вопрос

Для доказательства этого утверждения, можно воспользоваться методом математической индукции.

База индукции: для n=1, левая и правая части равны.

Предположение индукции: предположим, что формула верна для некоторого k, т.е. 0 + 1 + 2 + ... + k = k(k+1)/2.

Шаг индукции: Докажем, что если формула верна для k, то она также верна для k+1. Добавив к обеим сторонам выражения k+1, получим:

0 + 1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1)
= (k^2 + k + 2k + 2)/2
= (k^2 + 3k + 2)/2
= (k+1)(k+2)/2

Таким образом, мы доказали, что формула верна для всех натуральных чисел n, что и требовалось доказать.