Indukcja matematyczna

Indukcja matematyczna jest sposobem dowodzenia twierdzeń, zazwyczaj dla liczb naturalnych dodatnich. Polega ona na udowodnieniu prawdziwości twierdzenia dla liczby jeden, a następnie po przyjęciu, że twierdzenie jest prawdziwe dla liczby k, udowodnić, że jest ono prawdziwe dla k + 1. Metodę tę możemy modyfikować, aby udowadniać twierdzenia dla zbiorów różnych od liczb naturalnych dodatnich.

Indukcję matematyczną możemy intuicyjnie zrozumieć w ten sposób: skoro twierdzenie jest prawdziwe dla jedynki, a także jeśli jest prawdziwe dla k, to jest również prawdziwe dla k + 1, to za k możemy przyjąć właśnie liczbę jeden, wtedy k + 1 będzie równe 2, a więc twierdzenie jest również prawdziwe dla liczby 2. Skoro udowodniliśmy, że twierdzenie jest prawdziwe dla liczby 2, to przyjmując liczbę 2 za k, możemy je udowodnić także dla liczby 3. W ten sposób, podstawiając za k kolejne liczby naturalne jesteśmy w stanie udowodnić twierdzenie dla nich wszystkich.

Za pomocą indukcji matematycznej możemy udowodnić, że wszyscy jesteśmy łysi. Jeśli ktoś ma tylko jeden włos, ciągle nazywamy go łysym. Jeśli ktoś ma k włosów i jest łysy, to fakt, że wyrośnie mu jeszcze jeden włos na głowie nie sprawi, że przestanie być łysy.

Oczywiście dowód ten jest żartobliwy, ale pozwala łatwiej zrozumieć ideę indukcji matematycznej.

Przykład:
Udowodnij, że twierdzenie dla każdego .

Krok 1.: Udowodnij twierdzenie dla n = 1.

Krok 2.: Przyjmij, że twierdzenie jest prawdziwe dla n = k. Udowodnij twierdzenie dla n = k + 1.
przyjmujemy za prawdziwe

Ponieważ , to jeśli udowodnimy , to na pewno .

Ponieważ każda liczba spełnia warunek , to twierdzenie musi być prawdziwe dla każdej liczby naturalnej dodatniej.

Zadanie:
Wykaż, że dla dowolnego prawdziwe jest twierdzenie .
Rozwiązanie:
Krok 1.: Udowodnij twierdzenie dla n = 1

Krok 2.: Przyjmując prawdziwość twierdzenia dla n = k, udowodnij twierdzenie dla n = k + 1.
przyjmujemy za prawdziwe i obliczamy:

Doszliśmy do momentu, której lewa strona równania jest oczywiście równa prawej, więc udowodniliśmy twierdzenie dla wszystkich liczb naturalnych dodatnich.