Indukcja matematyczna - znajdź błąd w dowodzie bez bazy

Krok 1. Sprawdzamy rachunek w kroku. Rozwijamy lewą stronę:

$(k + 1)^2 + (k + 1) + 1 = k^2 + 2k + 1 + k + 1 + 1 = k^2 + 3k + 3.$

Prawa strona: $(k^2 + k + 1) + 2(k + 1) = k^2 + 3k + 3$. Rachunek jest poprawny, a wniosek „jeśli $k^2 + k + 1$ jest parzyste, to $(k + 1)^2 + (k + 1) + 1$ też” - również. Krok indukcyjny jest dobry.

Krok 2. Sprawdzamy bazę. Uczeń jej nie sprawdził. Dla $n = 1$: $1 + 1 + 1 = 3$ - liczba nieparzysta. Dla $n = 0$: $1$ - też nieparzysta. Baza nie zachodzi, więc „domino” nigdy się nie przewraca: krok przenosi prawdziwość z $k$ na $k + 1$, ale nie ma od czego zacząć.

Krok 3. Rozstrzygamy, jak jest naprawdę. Zapiszmy $n^2 + n + 1 = n(n + 1) + 1$. Iloczyn dwóch kolejnych liczb $n(n + 1)$ jest zawsze parzysty, więc $n(n + 1) + 1$ jest zawsze nieparzyste. Twierdzenie ucznia jest fałszywe dla każdego $n$.

(Ciekawostka: tym samym krokiem indukcyjnym można by „udowodnić” prawdziwe twierdzenie - że $n^2 + n + 1$ jest zawsze nieparzyste. Wtedy baza $n = 1$ zachodzi i dowód jest poprawny.)

Odpowiedź. Błąd polega na pominięciu bazy indukcji. Krok indukcyjny jest poprawny, ale bez sprawdzenia pierwszego przypadku nic nie dowodzi - a pierwszy przypadek jest fałszywy ($3$ jest nieparzyste). Liczba $n^2 + n + 1$ jest w rzeczywistości nieparzysta dla każdego $n$. Innym rodzajem błędu - zepsutym krokiem dla jednego $k$ - jest słynny dowód „wszystkie konie są tej samej maści”, opisany na stronie o indukcji.