Да, набросал несколько раз. Суть в том, что для n дисков нужно сначала отодвинуть верхние n-1, потом переместить самый большой, а затем вернуть эти n-1 обратно. Это требует 2·T(n‑1)+1 хода. Решение рекуррентного соотношения даёт T(n)=2ⁿ–1. Что касается нижнего предела, то самый большой диск может переместиться только один раз, и каждый меньший диск должен хотя бы один раз двигаться между штырями в обоих направлениях, поэтому обойти 2ⁿ–1 ходов невозможно. Шаг индукции просто подтверждает, что если для n-1 это сделать нельзя, то и для n не получится. Это элегантное, классическое доказательство – что-то вроде головоломки, которая показывает, насколько жёсткая может быть рекурсия.