Математика является наукой, строящейся исключительно на логических доказательствах, в отличие, например, от физики, где широко используются также эмпирические методы. Доказательством в математике называют логические умозаключения, которые гарантируют конкретный вывод для задачи с заявленными условиями. Доказанное утверждение может впоследствии использоваться для доказательства других утверждений. При этом существуют различные методы доказательства. Самым простым по смыслу является метод прямого доказательства, когда утверждение подтверждается с использованием уже доказанных ранее теорем как логическое следствие. Такой способ не всегда доступен или не всегда удобно применяется. Очень известен из школьного курса геометрии метод доказательства от противного, когда предполагается истинным утверждение, противоречащее интуитивным представлением. Если из такого предположения логически следует противоречие, сделанное предположение считается ложным и за истину принимается противоположное.
Но в этой статье мы обсудим метод математической индукции, который чем-то поход на эмпирический метод индукции, применяемый в физике, но отличается гарантированной надёжностью. Сам метод является очень простым и состоит из двух шагов: сначала доказывается некоторое базовое простое утверждение, а затем показывается, что для верной предыдущей итерации верна и последующая. Доказательство этих двух утверждений делает верным утверждение для любого номера N от базового номера до бесконечности. Это похоже на эффект домино: если толкнуть первую домино и каждая последующая падает, когда падает каждая предыдущая, падает вся конструкция.
Возможно, вы знаете, как посчитать сумму натуральных чисел от 0 до любого числа N, но давайте на примере этой задачи обсудим метод математической индукции. Для этого сначала начнем наблюдение за простыми суммами натуральных чисел и попробуем эмпирически получить формулу. Вот несколько первых сумм:
- i=1: si = 1 = 1;
- i=2: si = 1+2 = 3;
- i=3: si = 1+2+3 = 6;
- i=4: si = 1+2+3+4 = 10;
- i=5: si = 1+2+3+4+5 = 15.
Можно заметить, что сумма увеличивается нелинейно, причем с квадратичной нелинейностью, то есть через точки (i; si) можно провести параболу si = i^2/2 + i/2 = i(i+1)/2. Мы нашли предположительно верную формулу, но не доказали ее. Работает ли она для случая i = 1? Да, работает, сумма si = 1. Предположим, что она работает и для случая i = k и проверим, работает ли она и для случая i = k+1 при верной в случае i = k. Для этого запишем si (i = k+1) = (k+1)(k+2)/2 и упростим выражение: si (i = k+1) = k^2/2 + 3k/2 + 1 = k^2/2 + k/2 + k + 1 = si (i = k) + k+1. Что и требовалось доказать, сумма k+1 натуральных чисел на k+1 больше суммы k натуральных чисел.
Если интересны разные вопросы математики и физики, подписывайтесь и обсуждайте интересующие вас вопросы в комментариях!