Короткие заметки о математике и программировании

А давайте про принцип математической индукции

Можно просто писать программы. Можно просить нейронки писать программы. А ещё можно доказывать что программа работает корректно. У меня в голове достаточно часто звучит фразочка друга "Когда я программирую, я доказываю корректность программы. Когда доказательство сошлось, программа начинает работать"

Ну и с LLM не всё так просто. Самую клёвую на текущий момент модель для решения задач и доказательства теорем Гуглу удалось натренировать как раз с помощью систем, проверяющих корректность доказательства.

Ну так вот. Простые вещи самые сложные. Принцип математической индукции как раз с этой грядки. Для начала - зачем он нужен. Вы хотите доказать что какое-то утверждение верно всегда. Что значит "всегда"? - для любого натурального n оно верно.

Что за утверждения это могут быть?
Ну, например, "сумма первых n нечётных чисел равна n*n". Или "если кидать на плоскость n прямых, не особо прицеливаясь, то кусков будет n * (n + 1) / 2 + 1".

Зачем такие сложности?
Возьми, проверь несколько чисел и всё хорошо будет. Ых... Не выходит, к сожалению. Вот, например, говорят что n*n + n + 41 - простое число. Очень хочется поверить, потому что, пока берём 1, 2, 3, 4, 5, 6 - всё сходится. 43 - простое, 47 - тоже. Но если пойти чуть дальше, найдётся число, которое простым не будет. Как же быть?

Ну, вот мы и готовы сформулировать принцип матемтической индукции. Если удастся доказать что:

  1. Утверждение верно для n = 1

  2. Из верности утверждения для n следует верность этого утверждения для n + 1
    это будет означать что утверждение верно для любого n

    • называется "база математической индукции"
    • индуктивный переход

Почему это так?
Я себе болото с кочками представляю. На кочках номера 1, 2, 3, .... Болото большое, кочек много. Бесконечно много. Нам нужно понять, можно ли по всем кочкам пропрыгать.

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

Подробнее почитать можно у Шеня

А я шутку расскажу, которая хорошо позволяет запомнить этот принцип.

Утверждение: "В автобус вмещается n человек"
База: n = 1 - "Один человек в автобус вмещается" - верно
Индуктивный переход: "практика показывает, что сколь набитым автобус не был бы, ещё один человек в него влезет" - верно

Значит, в автобус влезет сколько хочешь людей. Хоть миллион, хоть миллиард.

#education #devTopic #junior