Метод математической индукции — инструмент, с помощью которого можно доказывать те или иные утверждения о числах. Он позволяет делать выводы и прогнозировать будущие значения чисел, используется в аналитике, чтобы предсказывать изменения показателей.
Рассказываем, что такое метод математической индукции, как он работает и для чего его используют в IT.
Индукция и дедукция: в чем разница
Индукцией в целом называют вид доказательства, когда общий вывод делается на основе частных наблюдений. Например:
Это существо с клыками, рыжее и полосатое. Мы знаем, что таким критериям отвечают тигры, так что это, должно быть, тигр. Или хотя бы кот.
Противоположный индукции метод — дедукция, когда выводы о частном случае делаются на основе общих знаний о каком-то явлении:
Все тигры полосатые и имеют большие клыки. Если мы встретим тигра — он, скорее всего, будет полосатым и клыкастым.
Доказательства по индукции и дедукции применяют в разных логических построениях. Методы применяют и по отдельности, и совместно. Кстати, «дедуктивный метод» Шерлока Холмса на самом деле основан скорее на индукции: детектив делал общие выводы о человеке на основе совокупности мелких признаков.
В математике индукцию используют по похожему принципу. Только вместо логических утверждений доказывают предположения о числах.
В чем заключается метод математической индукции
Математическая индукция помогает доказать истинность какого-то утверждения для всех натуральных чисел. Натуральными называются целые порядковые числа: 1, 2, 3 и так далее. Некоторые математики также включают в это множество ноль.
Идея метода в том, что если высказывание справедливо для любого произвольного числа в ряду, то оно будет верным для всех. Чтобы доказать это предположение, нужно проверить корректность высказывания для нескольких чисел: первого в ряду, произвольного k и следующего за ним k + 1.
Разберем принцип математической индукции пошагово.
Шаг 1. Формулировка утверждения. На этом этапе определяем утверждение, которое будем доказывать. Его можно описать в виде формулы. Классический пример — формула суммы арифметической прогрессии:
Сумма целых положительных чисел от 1 до N вычисляется по формуле N * (N + 1) / 2.
Проверим это утверждение с помощью метода математической индукции.
Шаг 2. База индукции. Базовый шаг или base case — это проверка корректности высказывания для самого первого числа в ряду. Как правило, это 0 или 1, но в зависимости от выбранного множества может быть и другое число. В случае с суммой целых чисел базисом будет число 1. Чтобы проверить истинность утверждения, подставим его в в формулу:
Sum = N * (N + 1) / 2
При N = 1
Sum = 1 * (1 + 1) / 2 = 1 * 2 / 2 = 1
Получается, что сумма всех чисел от 1 до 1 равна единице. Высказывание верно для базового числа.
Шаг 3. Предположение. Этот этап называют индукционным предположением. Вместо базового числа берется произвольное число k — мы предполагаем, что для числа k верно это утверждение. Считать на этом шаге пока не надо: просто допустить, что высказывание корректно для k.
Шаг 4. Индукционный шаг. Это последний и главный этап доказательства по методу математической индукции. Идея в том, что если высказывание справедливо для k, то оно будет верным и для k + 1. А так как k может быть любым, получается, что для каждого следующего числа утверждение окажется корректным.
Формула на этом этапе получается более сложная. Для нашего примера она будет выглядеть так:
k * (k + 1) / 2 + (k + 1) = (k + 1) * (k + 1 + 1) / 2
То есть:
- берется сумма чисел от 1 до k — на прошлом шаге мы предположили, что она равна k * (k + 1) / 2;
- к этой сумме прибавляется (k + 1) — следующее число ряда. Так получается сумма от 1 до (k + 1) — это и становится левой частью уравнения;
- в правой части используется та же формула, но вместо k в нее подставляется k + 1. Если высказывание верно, в результате вычислений получится та же самая сумма от 1 до k + 1.
После составления уравнения остается только выяснить, точно ли левая часть равна правой. Для этого нужно преобразовать и упростить формулу по законам алгебры:
k * (k + 1) / 2 + (k + 1) = (k + 1) * (k + 2) / 2 # складываем 1 + 1 в правой части и получаем 2
(k2 + k) / 2 + (k + 1) = (k2 + 3k + 2) / 2 # слева умножаем k * (k + 1), а справа — (k + 1) * (k + 2)
(k2 + k) + 2 * (k + 1) = k2 + 3k + 2 # умножаем обе стороны уравнения на 2, чтобы убрать деление
k2 + k + 2k + 2 = k2 + 3k + 2 # раскрываем скобки слева
k2 + 3k + 2 = k2 + 3k + 2 # складываем 2k и k, получаем 3k — левая и правая части стали одинаковыми
После преобразований видно, что обе части уравнения идентичны. Это значит, что равенство соблюдено — следовательно, выражение действительно истинно.
Конечно, этот пример базовый и довольно простой. Такие примеры и решения для метода математической индукции можно найти разве что в учебниках и задачниках по математике. А в реальности метод используют для более сложных доказательств, причем не только в фундаментальной науке, но и в решении прикладных задач.
Как математическую индукцию используют в анализе данных: примеры задач
С помощью метода математической индукции доказывают утверждения о бизнесе, ищут способы оптимизации для алгоритмов и выполняют множество других задач. Большинство из них так или иначе сводится к проверке формул. Вот несколько примеров ситуаций, в которых может помочь этот метод.
Расчеты в бизнесе и производстве. Скажем, можно проверить, точно ли текущего объема поставок товара хватит, чтобы удовлетворить спрос, если он стабильно растет. Или — верны ли формулы, по которым рассчитывается нужное количество слоев для печатной платы.
Создание аналитических моделей. Модели используются в аналитике, чтобы предсказывать какие-то будущие явления. С помощью индукции определяют, корректно ли работает модель. Например:
- выдает ли она верные результаты для произвольного временного промежутка N месяцев;
- правильно ли она моделирует распределение ресурсов между N предприятиями.
Аналитика процессов. В частности, рекурсивных — таких, где новые результаты зависят от предыдущих. С помощью индукции доказывают, что процесс корректен на каждом шаге, например проверяют, верна ли формула, по которой рассчитывается прирост аудитории. Или оценивают, корректен ли прогноз объемов добычи нефти на ближайший период — с учетом того, что добыча в этом периоде может зависеть от предыдущих результатов.
Проверка корректности данных. Индукцию можно применять и для проверки информации — скажем, доказать, что какие-то правила работы в компании выполняются из года в год. Или проверить, корректно ли вычисляют показатели эффективности сотрудников.
Оптимизация вычислений. Вычислительные алгоритмы можно улучшать, чтобы они работали быстрее, — например, использовать более простые формулы. А индукция позволяет проверить, точно ли новый алгоритм работает правильно для любых входных данных. Скажем, во всех ли случаях он сможет корректно вычислить дисперсию или отсортировать большой ряд чисел.
Доказательства с помощью индукции часто формулируют вручную. Можно написать алгоритм для проверки корректности высказывания, а можно взять уже готовый — но часто это дольше и сложнее, чем доказать вручную. В качестве вспомогательных инструментов также используют вычислительные системы, например MATLAB или Wolfram Alpha. А в последние года для проверки равенства выражений могут применять нейросети.
Подведем итог
- Математическая индукция — это метод, который позволяет проверить корректность какого-то высказывания о натуральных числах. Например, оценить, для любого ли числа верно сработает формула.
- Доказательство с помощью математической индукции состоит из нескольких шагов: формулировка утверждения, расчеты для базового числа, предположение и индукционный шаг. Если на последнем этапе числа совпали, значит, утверждение верно.
- Метод используют в анализе данных, Data Science, бизнес-аналитике, а также для проверки алгоритмов и создания вычислительных моделей. С его помощью проверяют корректность формул.
