Content Oriented Web
Make great presentations, longreads, and landing pages, as well as photo stories, blogs, lookbooks, and all other kinds of content oriented projects.

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

М
Определение
Математическая индукция – один из важных и достаточно широко используемых приемов математического доказательства. То есть, вообще говоря, дедуктивное умозаключение, опирающееся на устройство множества натуральных чисел, а именно – на аксиому индукции: если множество 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 колец.
Очевидно, что
n
Кстати, так мы можем
подсчитать число ходов в данном алгоритме.
Обозначим через T к минимальное число ходов,
которое необходимо, чтобы перенести башню из n колец.
Очевидно, что
Причем, исходя из структуры нашего решения, которое, возможно, и не оптимально, можно заключить, что
Причем, исходя из структуры нашего решения, которое, возможно, и не оптимально,
можно заключить, что
n
Выходит, что нет – так как
в тот момент, когда мы сможем переложить самое большое кольцо, башня из меньших колец должна вся находиться на каком-то одном стержне, а для этого требуется как минимум Tnn ходов.
Давайте подумаем, может ли быть решение с меньшим числом ходов?

Чтобы переложить большое кольцо, нужен как минимум
один ход, и затем Tnn ходов, чтобы переложить на него
башню из n 1 колец.
n1
n1
Выходит, что нет – так как в тот момент, когда мы сможем переложить самое большое кольцо, башня
из меньших колец должна вся находиться на каком-то одном стержне, а для этого требуется как минимум Tnn ходов.
Чтобы переложить большое кольцо, нужен как минимум
один ход, и затем Tnn ходов, чтобы переложить на него
башню из n 1 колец.
Давайте подумаем, может ли быть решение
с меньшим числом ходов?
И тут снова
на помощь приходит математическая индукция!
Все доказано.
И тут снова на помощь приходит математическая индукция!

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

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

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