Indukcja matematyczna to metoda dowodzenia twierdzeń, najczęściej dotyczących wszystkich liczb naturalnych. Intuicyjnie polega na dwóch krokach:

  • sprawdzeniu bazy indukcji — pokazaniu, że twierdzenie jest prawdziwe dla pierwszego przypadku (np. n = 1);
  • kroku indukcyjnym — udowodnieniu, że jeśli twierdzenie jest prawdziwe dla pewnej liczby n, to jest też prawdziwe dla liczby n + 1.

Gdy te dwa kroki zostaną wykonane, wnioskujemy, że twierdzenie jest prawdziwe dla wszystkich kolejnych liczb naturalnych: dla 1, potem dla 2, potem dla 3 i tak dalej.

Zasada działania (formalnie)

  • Ogłoś, że dowód będzie przez indukcję względem n n. ( nn )
  • Pokaż, że stwierdzenie jest prawdziwe dla n = 1 n.
  • Załóż, że stwierdzenie jest prawdziwe dla pewnego, dowolnego n n (to tzw. hipoteza indukcyjna).
    • Pokaż wtedy, że stwierdzenie jest prawdziwe dla następnej liczby, n + 1 {\displaystyle n+1}.

Przykład klasyczny: suma pierwszych n liczb naturalnych

Udowodnimy, że dla wszystkich liczb naturalnych n zachodzi wzór

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\i1} styropian 1+2+3+....{\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)}

Równoważnie można zapisać

2 ∑ k = 1 n k = n ( n + 1 ) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)}

Dowód przez indukcję na n:

Baza indukcji (n = 1):

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)}

Równość jest spełniona, więc baza indukcji jest prawdziwa.

Krok indukcyjny: Niech dla pewnego n0 zachodzi

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)}

Chcemy pokazać, że wtedy zachodzi równość dla n = n0 + 1:

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k}

Wyrażenie to można zapisać jako

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)}

Z hipotezy indukcyjnej mamy 2 ∑_{k=1}^{n_{0}} k = n_{0}(n_{0}+1), więc

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)}

Po podzieleniu obu stron przez 2 otrzymujemy postać znaną z tezy:

∑_{k=1}^{n_{0}+1} k = (n_{0}+1)(n_{0}+2)/2, czyli wzór prawdziwy także dla n = n0 + 1.

Skoro baza i krok indukcyjny zostały udowodnione, wniosek że wzór jest prawdziwy dla wszystkich n ∈ N jest poprawny.

Wariacje i uwagi praktyczne

  • Indukcja od dowolnego n0: nie zawsze zaczynamy od 1 — można zacząć od innej liczby początkowej n0 (np. n ≥ 0 lub n ≥ 2). Należy wtedy sprawdzić bazę dla tego n0.
  • Indukcja silna: zamiast zakładać prawdziwość tylko dla n, zakładamy prawdziwość dla wszystkich m ≤ n i na tej podstawie dowodzimy prawdziwość dla n+1. Przydatna, gdy wartość dla n+1 zależy na przykład od kilku poprzednich przypadków.
  • Indukcja strukturalna: uogólnienie indukcji na struktury złożone (np. drzewa, wyrażenia matematyczne) — stosowana w informatyce i logice.
  • Typowe błędy: pominięcie sprawdzenia bazy indukcji, dowodzenie kroku indukcyjnego nieprawidłowo (np. używanie tego, co chcemy udowodnić dla n+1), lub założenie czegoś więcej niż dopuszcza hipoteza indukcyjna.

Jak pisać dowód indukcyjny — praktyczne wskazówki

  • Zacznij od jasnego sformułowania tezy i określenia zakresu n (np. "dla wszystkich n ∈ N").
  • Wyraźnie zaznacz bazę indukcji i policz ją krok po kroku.
  • Sformułuj hipotezę indukcyjną: "Załóżmy, że twierdzenie jest prawdziwe dla pewnego, ale dowolnego n = n0".
  • W kroku indukcyjnym przekształcaj wyrażenie dla n0+1, korzystając jedynie z hipotezy indukcyjnej i algebraicznych przekształceń.
  • Na koniec napisz krótkie zdanie podsumowujące: z bazy i kroku wynika prawdziwość dla wszystkich n.

Indukcja matematyczna to potężne narzędzie — opanowanie jej technik pozwala dowodzić wielu własności ciągów, sum, nierówności, własności dzielnikowych i twierdzeń kombinatorycznych.