Indukcja matematyczna - wzór ogólny ciągu rekurencyjnego aₙ₊₁ = 2aₙ + 1

Krok 1. Liczymy wyrazy i zgadujemy wzór.

$a_1 = 1, \quad a_2 = 2 \cdot 1 + 1 = 3, \quad a_3 = 2 \cdot 3 + 1 = 7, \quad a_4 = 2 \cdot 7 + 1 = 15, \quad a_5 = 31.$

Każdy wyraz jest o $1$ mniejszy od potęgi dwójki: $2, 4, 8, 16, 32$. Przypuszczamy, że $a_n = 2^n - 1$.

Krok 2. Sprawdzenie dla n = 1 (baza). $a_1 = 1$ oraz $2^1 - 1 = 1$. Zgadza się.

Krok 3. Założenie i teza. Zakładamy, że $a_k = 2^k - 1$ dla pewnego $k \ge 1$. Teza: $a_{k + 1} = 2^{k + 1} - 1$.

Krok 4. Dowód kroku. Z definicji rekurencyjnej i z założenia:

$a_{k + 1} = 2a_k + 1 = 2\left(2^k - 1\right) + 1 = 2^{k + 1} - 2 + 1 = 2^{k + 1} - 1.$

To jest teza.

Odpowiedź. Na mocy zasady indukcji matematycznej $a_n = 2^n - 1$ dla każdego $n \ge 1$.

Ta rekurencja opisuje łamigłówkę wieże Hanoi: żeby przenieść $n + 1$ krążków, trzeba przenieść $n$ krążków na bok ($a_n$ ruchów), przełożyć największy ($1$ ruch) i znów przenieść $n$ krążków ($a_n$ ruchów). Dlatego minimalna liczba ruchów to $2^n - 1$ - dla $64$ krążków z legendy to ponad $1{,}8 \cdot 10^{19}$ ruchów.