Начнем с того, что такое математическая индукция.
Математическая индукция – метод математического доказательства, который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел, согласно Wikipedia. Говоря простыми словами, у нас есть какое-то математическое высказывание о натуральных числах, и мы хотим доказать/опровергнуть его истинность.
Разные источники дают разное определение натуральных чисел. В моем университете один профессор включает ноль во множество N, а по определению другого натуральные числа начинаются с единицы. Дело вкуса ;) Но очень важно понять, с каким именно множеством вы работаете. Позже узнаете, почему.
Конечно, если наше математическое высказывание (формула) относится к маленькому множеству чисел, то гораздо легче просто высчитать ответ в уме или ввести данные в Wolfram – на этом всё, пускайте титры.
Например, вы, убивая время в интернете, где-то прочли, что сумма положительных натуральных чисел от 1 до n, то есть, 1+2+3+...+n, вычисляется по формуле n*(n+1)/2. Допустим, у вас проблемы с доверием, и вы хотите проверить, работает ли эта формула на самом деле, или это просто часть всемирного заговора?
Эту формулу можно применить к маленьким множествам, так как вы можете легко вычислить сумму чисел от 1 до 10, от 1 до 20, от 1 до 50, а если вас замучила бессонница, то попробуйте посчитать не овечек, а сумму чисел от 1 до 100. Помогает. Иногда.
Потом остается только подставить значения в формулу и сравнить.
Но если мы говорим о множестве с большим количеством элементов или о бесконечном множестве, то именно тут и пригодится индукция.
Проверка высказывания для наименьшего числа – это начало индукции.
Мы начинаем с базиса (база, base case) – нам дано наименьшее число, для которого нужно проверить истинность высказывания. Обычно это 1, но могут быть и другие варианты, которые обязательно указываются в условии. Например, можно начать с 4 или 5. Это не так важно. Но иногда этот базис не указывается эксплицитно. В этом случае вы начинаете с наименьшего числа вашего множества. Поэтому важно знать, с чего начать. Уточните, включается ноль в N или нет. В примерах в этой статье множество натуральных чисел начинается с единицы.
Затем мы утверждаем, что выражение истинно для любого n>=1. Мы не знаем этого наверняка, конечно. Но мы предполагаем, что если утверждение истинно для любого n, то оно будет верно и для n+1. Это называется шагом индукции. А так как n – это любое число из множества N, то мы можем проверить математическое высказывание для очень-очень-очень больших чисел.
Итак, вернёмся к нашей формуле вычисления суммы чисел от 1 до n.
Начало индукции: проверяем, верна ли формула для n=1: n*(n+1)/2=> 1*(1+1)/2=1*(2)/2=1
Так как сумма чисел от 1 до 1 равна 1, то высказывание истинно для n=1.
Затем мы утверждаем, что математическое высказывание истинно для любого n>=1. То есть 1+2+3+...+n = n*(n+1)/2.
Переходим к шагу индукции – если высказывание верно для n, то оно истинно и для n + 1. 1+2+3+...+n + (n+1) = (n+1)(n+1 + 1)/2.
Левая часть уравнения – это сумма чисел от 1 до n+1. Мы заменили все n в правой части на n+1, так как мы больше не рассматриваем n, а доказываем, что высказывание истинно именно для n+1.
Если вы помните, то сумма чисел от 1 до n вычисляется по формуле n*(n+1)/2. Поэтому часть выражения справа (а именно 1+2+3+...+n) можно заменить на n*(n+1)/2.
У нас остается n*(n+1)/2 + (n+1) = (n+1)(n+1 + 1)/2. Нам нужно доказать или опровергнуть равенство этих двух выражений.
Всё, что происходит дальше – это чистая алгебра. Нам надо всего лишь упростить эти выражения, так как немного трудно что-либо сказать об их равенстве, просто посмотрев на них. Даже если вы своими эльфийскими глазами можете рассмотреть, чему равны обе части, с вас всё равно потребуют формальное доказательство.
Немного упрощаем правую сторону:
n*(n+1)/2 + (n+1) = (n+1)(n+2)/2
Затем раскрываем скобки справа (умножаем n*(n+1)) и слева (умножаем (n+1)(n+2)). Получается (n^2 +n)/2 + (n+1) = (n^2 +3*n + 2)/2
Умножаем обе части уравнения на 2, чтобы избавиться от знаменателя:
(n^2 +n) + 2*(n+1) = (n^2 +3*n + 2)
Раскрываем скобки и упрощаем:
n^2 +n + 2*n+2 = n^2 +3*n + 2
Так как n + 2*n в левой части можно записать в виде 3*n, упрощаем левую часть:
n^2 +3*n+2 = n^2 +3*n + 2
Мы получаем идентичные выражения справа и слева, что означает, что истинность выражения доказана.
Многие из тривиальных алгебраических преобразований сверху можно пропустить, если вы сильны в математике. Но иногда формулы довольно громоздкие, поэтому я бы рекомендовала подробно описывать каждый вычислительный шаг. Так гораздо легче предотвратить и найти ошибки, если таковые имеются( а они очень часто имеются).
Рассмотрим другой пример. Попробуем доказать, что 1 + 3 + 5 + 7 + · · · + (2n − 1) = n^2. Эта формула описывает сумму нечетных чисел, начиная с 1.
1. Начинаем с базиса. Проверяем, истинно ли высказывание для n=1:
n^2 = 1^2 = 1
Сумма нечетных чисел от 1 до 1 равна 1, что действительно так. Чудеса!
2. Затем утверждаем, что выражение истинно для какого-то n>=1, то есть 1 + 3 + 5 + 7 + · · · + (2n − 1) = n^2.
3. Утверждаем, что если высказывание истинно для n, то оно также верно для n+1 (шаг индукции).
Проверяем для n+1:
1 + 3 + 5 + 7 + · · · + (2n − 1) + (2*(n+1)´-1) = (n+1)^2
(2*(n+1)´-1) – это следующее после (2n − 1) нечетное число.В данном случае прибавить n+1 к выражению слева нельзя, как мы это сделали в предыдущем примере, так как если n=999, то n+1 = 1000, что не является нечетным числом. Нам-то нужны исключительно нечетные. А они представлены именно формулой (2n − 1). Иногда в задаче указан определенный паттерн, который нужно учесть, составляя формулы для правой и левой части уравнения.
Можно упростить (2*(n+1)´-1) и получить (2n+1).
1 + 3 + 5 + 7 + · · · + (2n − 1) +(2n+1) = (n+1)^2
Но мы еще не закончили вычисления!
В правой части заменяем 1 + 3 + 5 + 7 + · · · + (2n − 1) на n^2, так как мы именно это взяли за основу в пункте 2. Раскрываем скобки в правой части. Наконец нам понадобилась одна из формул сокращённого умножения, вау!
Подставляем:
n^2 + (2n+1) = n^2 + 2n + 1
Отбрасываем скобки в левой части:
n^2 + 2n+1 = n^2 + 2n + 1
Правая и левая часть уравнения совпадают. Значит, математическое высказывание истинно.
Математическую индукцию еще сравнивают с эффектом домино. Если косточки домино выстроены в ряд, и какая-то упадёт, приложившись к следующей и опрокинув её, то та, в свою очередь, опрокинет следующую, и за ней последуют все остальные. А если мы опрокинем первую косточку, то упадёт весь ряд.
В индукции, если высказывание истинно для натурального числа, с которого мы начинаем, например, 8, то оно истинно для 9. Если оно истинно для 9, то оно верно для 10. И так далее. До бесконечности. Это мы и пытаемся доказать. Есть задачи, которые имею несколько базисов. Например, вам надо проверить какое-то высказывание для n=4, n=5, n=6 в начале индукции. Попадаются и задачи, где база дана в рекурсивной форме.
Потренируйтесь на других примерах. Основным скилом для решения подобных задач является умение находить паттерны. Вы также должны понимать, что именно вы хотите доказать? Что описывает формула? Очень важно знать и уметь применять некоторые формулы, которые помогут вам упростить выражения. Например, те же самые формулы сокращённого умножения. Они очень часто встречаются в математической индукции. Очень многие допускают ошибки именно в конце, когда надо подключить свои знания алгебры.
Помните, что математическая индукция применяется только к высказываниям с натуральными числам. Ваш n не может равняться -10 или 8.5. Дискриминация по отношению к действительным и комплексным числам? Вполне может быть.
Для чего же это всё?
Во-первых, решая подобные задачи, вы развиваете логику и алгоритмическое мышление, что играет не последнюю роль в программировании. Вы учитесь распознавать всякого рода паттерны.
Во-вторых, если вы внимательнее посмотрите на принцип математической индукции, вы заметите, что это чистейшая рекурсия. Предполагаю, что вы знакомы с рекурсией, если вы хотя бы немного программируете. Есть base case – условие завершения алгоритма. Также есть правило перехода. И чтобы проверить высказывание для n, нужно решить что-то для n-1, а потом с помощью алгебры дойти до n.
Рекурсию можно или любить, или люто ненавидеть. Но если ее понять и правильно использовать, она может сделать код элегантнее.
Комментарии