indukcja matematyczna minnie: Wieże z Hanoi. Na desce znajdują się 3 pręty, na jednym z nich znajduje się n krążków o różnych średnicach ułożonych w kolejności średnic od największego na dole do najmniejszego na górze. Należy przenieść całą wieże na drugi pręt korzystając z trzeciego w ten sposób, ze w jednym ruchu można przenieść tylko jeden krążek i nie można położyć większego na mniejszym. Jaka jest najmniejsza ilość ruchów, przy której można to uczynić?

123: 2ⁿ − 1

Trivial: Klasyczny problem, który łatwo rozwiązać rekurencją. Najpierw warunek początkowy. Dla n = 1 musimy wykonać tylko jeden ruch aby przenieść krążek. a₁ = 1 Dla n krążków potrzebujemy tyle ruchów: 1. Przenosimy n−1 górnych krążków na trzeci pręt. 2. Przenosimy ostatni krążek na drugi pręt. 3. Przenosimy n−1 krążków z trzeciego pręta na drugi. Zatem: a_n = a_n−1 + 1 + a_n−1 = 2a_n−1 + 1. Trzeba rozwiązać to równanie rekurencyjne. Można to zrobić np. tak: a_n = 2a_n−1 + 1 = 2(2a_n−2 + 1) + 1 = 2²a_n−2 + 2 + 1 = 2³a_n−3 + 2² + 2 + 1 = 2⁴a_n−4 + 2³ + 2² + 2 + 1 = 2^ka_n−k + ∑_m=0..k−1 2^m Podstawiamy k=n−1 i mamy: a_n = 2ⁿ⁻¹*a₁ + ∑_m=0..n−2 2^m = 2ⁿ⁻¹ + 2ⁿ⁻¹ − 1 = 2ⁿ − 1.