Как доказать

[The Nameless One]

Как доказать тот факт, что сумма целых чисел от 1 до N равна (N * (N+1)) / 2 ?
Как это вывели, помогите понять, пожалуйста!

[Dale]

Попробуйте для начала проверить это на нескольких конкретных примерах. По ходу станет совершенно очевидно, вывод очень простой.

[The Nameless One]

Проверил в уме на 1 + 2 + 3 + 4 + 5  = (5 * 6) / 2 = 15.
Возможно я туговат в таких вещах, но сформулировать доказательство словами не могу, так, что-то на уровне интуиции

[Dale]

Попробуйте теперь складывать числа не подряд, а парами: первое с последним, второе - с предпоследним и т.д.
Для простоты сначала возьмем четное число элементов, чтобы все числа сложились в пары. Скажем, попробуйте для ряда от 1 до 10.

[Sla]

шаг арифметической прогрессии чисел от 1 до N  равен 1
если принять первый за А, а шаг за d, последний за  N

A + (A + d) + (A + d +d ) ... и так N раз

а че я стараюсь? это вон в википедии есть  http://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F

[Алексей++]

The Nameless One, подсказка:

(N * (N+1)) / 2  - площадь прямоугольного треугольника

[The Nameless One]

Dale, Sla и Алексей1153++, спасибо!

[Dale]

Теперь понятен вывод формулы?
Для нечетных N тоже вывели?

[Dale]

P.S. Настоятельно рекомендую проштудировать вот эту книгу:

Просто необходимый математический ликбез для программиста. Ликвидирует практически все пробелы в знаниях. По этой учебной программе сам Дональд Кнут учит своих студентов.

Книга не из самых дешевых, но стоит каждой заплаченной за нее копейки.

[Алексей++]

конкретная такая книга

[Dale]

Да, для чиста конкретных пацанов-программистов. Кирпич весьма увесистый.

[Вад]

Поскольку слово "математическая индукция" не прозвучало, то, наверное, стоит его озвучить
Шаг 1. Проверяем формулу для n=1. Очевидно, что 1*2/2 = 1, сумма верная
Шаг 2. Предположим, что для некоторого N=k всё работает. Т.е. Sum(k) = k(k+1)/2
Шаг 3. Проверим, как всё работает для k+1, сводя задачу к предыдущей: Sum(k+1) = (k+1) + Sum(k) = k + 1 + (k(k+1))/2 = (k(k+1) + 2(k+1)) / 2 = (k+2)(k+1) / 2. Что и требовалось доказать.
Поскольку из истинности k-того шага следует истинность k+1-го шага, и шаг для 1 верен, то индуктивно (рекурсивно) формула выводится для любого положительного целого N.

(Это что касается доказательства корректности, а не вывода, конечно )

[Алексей++]

вот так нагляднее некуда )) Хоть и не про войну.



12345  <<складываемые числа
     
    *
   **  << высота==5
  ***
 ****
*****  <<длина основания==5
     

площадь была бы 5*5/2, но учитываем, что диагональ добавляет 1/2 единицы площади за каждый элемент

S = (5*5/2) + (5/2)= N*N/2 + N/2 = (N+1)*N/2

[The Nameless One]

Да, спасибо огромное, мужики! Теперь понял все.
И за книгу отдельное спасибо - очень нужная книженция, приобрету обязательно!

[Джон]

P.S. Настоятельно рекомендую проштудировать

Есть в ней серьёзные отличия от первого издания 1998 года? Та шла под подзаголовком "Основание информатики".

конкретная такая книга

Кстати, "конкретная" в данном случае акроним (наверное) "КОНтинуальная и дисКРЕТНАЯ" англ. CONCRETE -> СONtinous и disCRETE

[Dale]

Есть в ней серьёзные отличия от первого издания 1998 года? Та шла под подзаголовком "Основание информатики".

В оглавлении вообще не обнаружил никаких отличий. Второе издание имеет больше страниц (784 против 703), но это вполне может объясняться другой версткой. Другое издательство - "Вильямс" (первое - "Мир"), другой переводчик.

Кстати, это повторный перевод того же первоисточника, так что отличия, наверное, и искать не стоит (кроме примечаний переводчика).

Кстати, "конкретная" в данном случае акроним (наверное) "КОНтинуальная и дисКРЕТНАЯ" англ. CONCRETE -> СONtinous и disCRETE

Точно. И вдобавок еще один каламбур - "concrete" означает бетон. Кагбэ намек на фундаментальность.

[Джон]

Ок, у меня просто 98-го года, а эта 2010-го, думал обновить, книга действительно мастхэв.