Примеры математической индукции

Задача на решение индукцией:
На один из трех штырьков насажены п различных колец так, что большее кольцо лежит ниже меньшего (на рисунке 3 п = 3). За один ход разрешается перенести одно кольцо с одного штырька на другой, при этом не разрешается большее кольцо класть на меньшее. Докажите, что наименьшее число ходов, за которое можно перенести все кольца с одного штырька на другой, равно 2n − 1.
Помощь и "решебника":
Условие этой задачи учителю лучше сформулировать самому. Тогда у учащихся будет возможность поучаствовать в поиске формулы, выражающей зависимость числа ходов от числа колец, и убедиться, что, даже найдя эту формулу, они пока что не могут доказать ее для любого натурального n, так как натуральных чисел бесконечно много.
Рассуждения можно провести так.
Одно кольцо (n = 1) можно перенести на новый штырек за 1 ход.
Два кольца (n = 2) можно перенести за 3 хода (первое кольцо перенести на второй штырек, второе — на третий, затем первое — на третий).
Три кольца (n = 3) можно перенести за 3 + 1 + 3 = 7 ходов, перенеся сначала два верхних кольца за 3 хода, потом нижнее кольцо за 1 ход, потом снова два кольца за 3 хода.
Аналогично можно перенести 4, 5, 6 колец за 15, 31, 63 хода соответственно.
Наблюдательные учащиеся могут заметить, что для п колец число ходов меньше n-й степени числа 2 на единицу, т. е. выражается формулой 2n − 1.
Следовательно, получена гипотеза о выражении числа ходов через n, которую еще нужно доказать для любого натурального n. Но что значит доказать формулу для любого натурального n? Очевидно, что проверить истинность формулы для всех n невозможно. Необходимо соглашение, позволяющее считать, что при выполнении некоторых условий доказываемое утверждение истинно для любого натурального n.
После обсуждения рассмотренных примеров учащиеся будут подготовлены к тому, что если истинность некоторого утверждения, зависящего от натурального n, установлена для n = 1 и доказано, что из истинности этого утверждения для некоторого п = k следует его истинность для следующего значения n, равного k + 1, то считается, что это утверждение истинно для любого натурального n (такое соглашение и называют принципом математической индукции).
Пример 1 из учебника достаточно прост, чтобы, не отвлекаясь на технические сложности, освоить идею доказательства методом математической индукции.

0

Сообщение от gregoro т. е. выражается формулой 2n − 1.

Для n=3

Сообщение от gregoro за 3 + 1 + 3 = 7 ходов

а 2n-1=5
Для n=4 7+1+7=15, а 2n-1=7
Что-то у Вас не то с формулой

0

n²-1 для всех, кроме n=1
Вики: Ханойская башня

0