Задача о ханойской башне

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

Пусть Pn есть минимальное число перекладываний дисков для перемещения башни с одного колышка на другой. Ясно, что Р1 равно единице.

Легко показать, что имеет место соотношение:

. (*)

Получить это соотношение можно из следующих соображений. Переместим на один из колышков n-1 дисков. Последний, самый большой диск, переместим на свободный колышек – одно перемещение. Башню из n-1 диска перемещаем на колышек, на котором находится самый большой диск - перемещение.

Итак, мы получили соотношение (*). Для получения значения сделаем замену переменных , тогда для получаем:

.

Повторяя это рекуррентное соотношение получаем:

.

Из условия следует, что . Окончательно . Для искомой величины получаем

.