Это из­вест­ная за­да­ча о Ха­ной­ской башне, ко­то­рую часто рас­смат­ри­ва­ют среди пер­вых задач на метод ма­те­ма­ти­че­ской ин­дук­ции. Соб­ствен­но го­во­ря, для ре­ше­ния этой за­да­чи нам не тре­бу­ет­ся ис­поль­зо­вать метод ма­те­ма­ти­че­ской ин­дук­ции, по­сколь­ку в ее усло­вии дано кон­крет­ное число колец. Разо­брав слу­чаи по­лу­чим, что по­тре­бу­ют­ся, со­от­вет­ствен­но, одно, три или семь пе­ре­кла­ды­ва­ний. Для того, чтобы пе­ре­ло­жить «башню» из че­ты­рех колец, не­об­хо­ди­мо: снять верх­ние три коль­ца, затем пе­ре­ло­жить ниж­нее коль­цо на сво­бод­ную па­лоч­ку и, на­ко­нец, по­ло­жить на него три коль­ца мень­ше­го диа­мет­ра. Таким об­ра­зом, по­тре­бу­ют­ся пе­ре­кла­ды­ва­ний. Решим за­да­чу для про­из­воль­но­го числа n колец. Из при­ве­ден­но­го рас­суж­де­ния сразу сле­ду­ет ре­кур­рент­ная фор­му­ла для чисел p_n наи­мень­ше­го числа пе­ре­кла­ды­ва­ний для башни, со­сто­я­щей из n колец:

Дей­стви­тель­но, для того, чтобы пе­ре­ло­жить ниж­нее, -е, коль­цо, нам вна­ча­ле надо пе­ре­ло­жить n ле­жа­щих над ним колец, на что будут за­тра­че­но p_n пе­ре­кла­ды­ва­ний. Затем мы пе­ре­ло­жим ниж­нее коль­цо и по­тра­тим еще p_n пе­ре­кла­ды­ва­ний, чтобы по­ме­стить на нем n верх­них колец. Не­труд­но до­га­дать­ся, что После этого оста­лось сде­лать по­след­ний шаг, со­сто­я­щий в при­ме­не­нии ме­то­да ма­те­ма­ти­че­ской ин­дук­ции для до­ка­за­тель­ства най­ден­ной фор­му­лы. Таким об­ра­зом, оста­лось ре­шить сле­ду­ю­щую за­да­чу: из­вест­но, что и для всех n До­ка­жи­те, что База ин­дук­ции: Ин­дук­ци­он­ный пе­ре­ход: если то

За­да­ча о ха­ной­ской башне яв­ля­ет­ся одной из луч­ших задач на ин­дук­ци­он­ный метод рас­суж­де­ния, в ее ре­ше­нии соб­ствен­но «метод ма­те­ма­ти­че­ской ин­дук­ции» иг­ра­ет не слиш­ком со­дер­жа­тель­ную роль. Ана­лиз при­ве­ден­но­го ре­ше­ния по­ка­зы­ва­ет, что су­ще­ство ре­ше­ния  — в по­стро­е­нии так на­зы­ва­е­мо­го ре­кур­сив­но­го ал­го­рит­ма.

Ответ: