Indukcja matematyczna — efekt domina

Co się właśnie stało?

Rząd kostek domina przewraca się w całości tylko wtedy, gdy pchniesz pierwszą kostkę i każda przewrócona sięga następnej. Zabierz start albo zrób za dużą przerwę — lawina się nie rozpocznie lub zatrzyma. Dokładnie tak działa dowód indukcyjny.

Zasada indukcji matematycznej:

Aby udowodnić, że twierdzenie $T(n)$ zachodzi dla wszystkich $n \in \mathbb{N}$, wystarczy pokazać dwie rzeczy:

Krok bazowy to „przewrócenie pierwszej kostki", a krok indukcyjny to gwarancja, że „każda przewrócona kostka przewraca następną". Razem pokrywają nieskończenie wiele przypadków skończonym rozumowaniem.

Klasyczny przykład — suma kolejnych liczb:

Krok bazowy $(n=1)$:

Krok indukcyjny — zakładamy $T(n)$ i dowodzimy $T(n+1)$:

To dokładnie wzór $T(n+1)$. Prawdziwość „przeniosła się" z $n$ na $n+1$ — a skoro startuje od $n=1$, obejmuje wszystkie liczby naturalne.

Dlaczego kilka przypadków to za mało?

Nawet sprawdzenie tysiąca pierwszych $n$ nie dowodzi niczego o $n = 10^6+1$. Kostek jest nieskończenie wiele — trzeba udowodnić implikację $T(n)\Rightarrow T(n+1)$, która działa zawsze, a nie tylko na wybranych przykładach.

Po co Ci to na maturze:

Indukcja to fundament dowodów wzorów na sumy ciągów, nierówności i podzielności — obowiązuje na maturze rozszerzonej. Schemat jest zawsze ten sam: sprawdź $T(1)$, załóż $T(n)$, wyprowadź $T(n+1)$.

Pierwsze rygorystyczne użycia tej metody to Francesco Maurolico (1575) i Blaise Pascal w „Traité du triangle arithmétique" (1654); jako aksjomat liczb naturalnych sformalizował ją Giuseppe Peano (1889).

Zapamiętaj: przewróć pierwszą kostkę (krok bazowy) i zadbaj, by każda przewracała następną (krok indukcyjny) — a przewrócą się wszystkie. Oba warunki są konieczne.