Моделирование с помощью рекуррентных отношений

В игре Ханойские башни есть n колец разного размера и три стержня. Кольца начинаются с первого стержня и располагаются по размеру так, чтобы самое большое из них находилось внизу. Цель игры состоит в том, чтобы все кольца оказались на другом стержне, по-прежнему в порядке убывания размера. Ни в коем случае нельзя размещать кольцо большего размера поверх кольца меньшего размера.

Пусть Hₙ - минимальное количество ходов, необходимое для завершения игры с n кольцами

а) Найдите значения H₁ и H₂. Стратегия игры следующая:

• Переместите все кольца, кроме самого большого, на второй стержень.
• Переместите самое большое кольцо на третий штифт.
• Все остальные кольца переместите со второй булавки на третью.

б) Объясните, почему, если следовать этой стратегии, Hₙ = 2Hₙ₋₁ +1.

в) Найдите формулу общего члена для Hₙ и минимальное количество ходов, необходимое для завершения игры с 10 кольцами.