Математическая индукция

Определение

Математическая индукция – один из важных и достаточно широко используемых приемов математического доказательства. То есть, вообще говоря, дедуктивное умозаключение, опирающееся на устройство множества натуральных чисел, а именно – на аксиому индукции: если множество E таково, что 1 ti E и из того, что натуральное число n ti E следует, что n + 1 ti E, то E = n .

Например,
в высказываниях

Математическая индукция – один из важных и достаточно широко используемых приемов математического доказательства.
То есть, вообще говоря, дедуктивное умозаключение, опирающееся на устройство множества натуральных чисел, а именно – на аксиому индукции: если множество E таково, что 1 ti E и из того,
что натуральное число n ti E следует, что n + 1 ti E, то E = n .

Если совсем неформально, но очень образно –
то математическая индукция – это утверждение
о том, что мы в состоянии подняться по лестнице
сколь угодно высоко, зная, что мы можем подняться
на нижнюю ступеньку (база индукции), и с каждой ступеньки можем перейти на следующую (индукционный переход).

Множество E часто удобно мыслить как подмножество таких натуральных чисел, для которых выполнено некоторое свойство Р. В такой интерпретации аксиома индукции утверждает, что если какое-то свойство выполнено для единицы, и из того, что оно выполнено для произвольного натурального n, следует, что оно также выполняется и для числа n + 1, то это свойство верно для всех натуральных чисел.

Если совсем неформально,
но очень образно –
то математическая индукция –
это утверждение о том,
что мы в состоянии подняться
по лестнице сколь угодно высоко, зная, что мы можем подняться
на нижнюю ступеньку (база индукции), и с каждой ступеньки можем перейти на следующую (индукционный переход).

Ну, например, пусть утверждается, что сумма ряда

Свойство может формулироваться настолько причудливо, что в нем не сразу усмотришь свойство именно какого-то натурального числа.

Свойство может формулироваться настолько причудливо,
что в нем не сразу усмотришь свойство именно какого-то натурального числа.

Так вот на такое равенство
можно смотреть как на сложное свойство натурального числа n: «сумме степенного ряда такого-то вида со старшей степенью n равняться такому-то выражению».

В частности, это свойство
числа 1, поскольку

В частности, это свойство числа 1, поскольку

Так вот на такое равенство можно смотреть
как на сложное свойство натурального числа n:
«сумме степенного ряда такого-то вида
со старшей степенью n равняться такому-то выражению».

Можно «руками» убедиться,
что данное равенство есть
также свойство двойки:

Можно «руками» убедиться, что данное равенство есть также свойство двойки:

Теперь предположим,
что данное свойство выполняется для числа n – 1, т. е. Пускай верно

В доказательствах по индукции выполнимость свойств
для маленьких натуральных n – в частности, для единицы – называют базой индукции

В доказательствах
по индукции выполнимость свойств
для маленьких натуральных n –
в частности, для единицы – называют базой индукции

Теперь предположим, что данное свойство выполняется для числа n – 1, т. е. пускай верно

(это называют индукционным предположением)

Будет ли из этого предположения следовать, что

Вопрос

Давайте сделаем этот переход –
он в данном случае несложный:
Коль скоро по индукционному предположению

Вопрос

Доказательство того,
что да – таки будет, называют при этом индукционным переходом.

Доказательство того, что да – таки будет, называют при этом индукционным переходом.

Давайте сделаем этот переход – он в данном случае несложный: Коль скоро по индукционному предположению

Индукцией доказывается существование решения
у популярной в XIX веке головоломки «Ханойские башни»:

Ее в 1883 году придумал французский математик
Эдуард Люка.
Изначально игра заключалась в том, чтобы башню из 8 убывающих
в диаметре колец перенести
с одного стержня на другой за наименьшее число ходов, не перенося за один ход несколько колец, и не укладывая большее кольцо на меньшее.

Будет ли из этого предположения следовать, что

Эдуард Люка

Ее в 1883 году придумал французский математик
Эдуард Люка. Изначально игра заключалась в том,
чтобы башню из 8 убывающих в диаметре колец перенести
с одного стержня на другой за наименьшее число ходов,
не перенося за один ход несколько колец, и не укладывая большее кольцо на меньшее.

С первого взгляда не очевидно даже то, что задача вообще имеет решение. Мы сначала докажем методом математической индукции, что задача имеет решение для любого произвольного числа n колец.

База индукции: «башню» из 1 кольца
всегда можно перенести на соседний стержень.
Убедимся, что башня из двух колец также переносится:

Теперь пусть башня состоит
из трех колец. Алгоритм для перенесения башни из двух
колец у нас уже имеется – поэтому применим его, затем перенесем самое большое кольцо на средний стержень, и применим алгоритм еще раз:

Будет ли из этого предположения следовать, что

Таким образом, мы видим,
что имея, как сказали бы программисты, процедуру,
или программу по переносу
башни из n колец, мы умеем переносить и башню из n + 1 кольца, так сказать, вызывая дважды процедуру переноса башни из n колец как подпрограмму.

Таким образом, мы видим,
что имея, как сказали бы программисты, процедуру, или программу
по переносу башни из n колец, мы умеем переносить и башню из n + 1 кольца, так сказать, вызывая дважды процедуру переноса башни из n колец как подпрограмму.

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

Будет ли из этого предположения следовать, что

Обозначим через T
минимальное число ходов,
которое необходимо, чтобы перенести башню из n колец.
Очевидно, что

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

Обозначим через T к минимальное число ходов,
которое необходимо, чтобы перенести башню из n колец.
Очевидно, что

Причем, исходя из структуры нашего решения, которое, возможно, и не оптимально, можно заключить, что

Причем, исходя из структуры нашего решения, которое, возможно, и не оптимально,
можно заключить, что

Выходит, что нет – так как
в тот момент, когда мы сможем переложить самое большое кольцо, башня из меньших колец должна вся находиться на каком-то одном стержне, а для этого требуется как минимум Tnn ходов.

Давайте подумаем, может ли быть решение с меньшим числом ходов?

Чтобы переложить большое кольцо, нужен как минимум
один ход, и затем Tnn ходов, чтобы переложить на него
башню из n − 1 колец.

n−1

Выходит, что нет – так как в тот момент, когда мы сможем переложить самое большое кольцо, башня
из меньших колец должна вся находиться на каком-то одном стержне, а для этого требуется как минимум Tnn ходов.

Давайте подумаем, может ли быть решение
с меньшим числом ходов?

И тут снова
на помощь приходит математическая индукция!

Все доказано.

И тут снова на помощь приходит математическая индукция!

Написать в чат

Есть вопросы по материалу?

Вы можете задать их в нашем специальном чате. Мы поможем разобраться в теме лучше

Понравилась статья?