Indukcja matematyczna

Z Nonsensopedii, polskiej encyklopedii humoru

Przybornik do przeprowadzania dowodów indukcyjnych

Indukcja matematyczna – zabawka matematyczna, służąca do pokazywania prawdziwości różnych twierdzeń matematycznych wątpliwej przydatności. Potężne narzędzie w rękach doświadczonych matematyków, czy akademicka fanaberia służąca do pobierania grantów i oblewania studentów? Zadecydować musisz sam.

Spis treści

1 Schemat ogólny
2 Historia wynalazku indukcji matematycznej
3 Indukcja niezupełna
4 Indukcja matematyczna a teoria gry w domino
5 Przykłady wykorzystania

[edytuj] Schemat ogólny

Każdy dowód matematyczny przeprowadzony przy pomocy indukcji matematycznej sprowadza się do następującego schematu:

Wskazujesz jeden lub więcej konkretnych przykładów potwierdzających prawdziwość twojego twierdzenia. Jest to tak zwana baza indukcji.
Zakładając, że twoje twierdzenie jest prawdziwe dla dowolnej liczby przypadków, dowodzisz, że jest ono prawdziwe również dla dowolnej plus jeden liczby przypadków. Jest to tak zwany krok indukcyjny.

[edytuj] Historia wynalazku indukcji matematycznej

Indukcja matematyczna została wynaleziona w Laboratoriach Bella w okresie największego postępu elektryfikacji miast i wsi. Miała ona stanowić tani substytut cewek indukcyjnych dla ubogich państw, które też chciały się podłączyć do sieci 220V. Cewki matematyczne składały się z cegły i wydruku dowodu (oczywiście indukcyjnego) na fakt, że zestaw ten jest układem inercyjnym, tj. gromadzi energię w wytwarzanym polu magnetycznym. Idea cewek matematycznych została porzucona ze względu na dużą zawodność tych układów. ^{[potrzebne źródło]}

[edytuj] Indukcja niezupełna

Jest to szczególny rodzaj indukcji matematycznej. Polega na tym, że wystarczy wykazać prawdziwość twierdzenia dla n=1, n=2 i n=3. Wtedy na mocy indukcji niezupełnej dla pozostałych n twierdzenie jest prawdziwe.

[edytuj] Indukcja matematyczna a teoria gry w domino

Zasada indukcji matematycznej została wywiedziona wprost z zasad gry zwanej efektem domina. Gra ta polega na układaniu długiego ciągu klocków domina, tak by w finale każdy klocek, popchnięty przez swojego poprzednika, popchnął i przewrócił swojego następnika. Grający w Domino matematycy zauważyli prosty fakt: zamiast ustawiać mozolnie klocki w odpowiedni ciąg, wystarczy logicznie uzasadnić dwie rzeczy: ktoś popchnie pierwszy klocek oraz to, że jeżeli jakiś klocek zostanie przewrócony, to przewróci on także swojego następnika. Z tej genialnej w swojej prostocie reguły narodziła się zasada indukcji matematycznej.

[edytuj] Przykłady wykorzystania

[edytuj] Parzystość wszystkich liczb

Korzystając z indukcji matematycznej można udowodnić, że wszystkie nieujemne liczby całkowite są parzyste.

Baza: 0 jest liczbą całkowitą nieujemną i parzystą.
Krok indukcyjny dla n: Załóżmy, że dla każdego k takiego, że k<n liczba k jest parzysta (założenie indukcyjne). Liczbę n można przedstawić w postaci n₁ + n₂, gdzie n₁, n₂<n. Ponieważ zgodnie z założeniem indukcyjnym n₁ i n₂ są parzyste, to ich suma też jest liczbą parzystą. A więc n jest liczbą parzystą. ∎

[edytuj] Nieparzystość wszystkich liczb

Korzystając z indukcji matematycznej można udowodnić, że wszystkie dodatnie liczby całkowite są nieparzyste.

Baza: 1 jest liczbą całkowitą dodatnią i nieparzystą.
Krok indukcyjny dla n: Załóżmy, że dla każdego k takiego, że k<n liczba k jest nieparzysta (założenie indukcyjne). Liczbę n można przedstawić w postaci n₁ + n₂ + 1, gdzie n₁, n₂<n. Ponieważ zgodnie z założeniem indukcyjnym n₁ i n₂ są nieparzyste, to ich suma plus 1 jest liczbą nieparzystą. A więc n jest liczbą nieparzystą. ∎

[edytuj] Wieczna środa

Korzystając z indukcji matematycznej można udowodnić, że w rzeczywistości, każdy dzień tygodnia jest środą.

Baza: Za co najwyżej 6 dni na pewno będzie środa. Równocześnie ostatnia środa skończyła się także co najwyżej 6 dni temu.
Krok indukcyjny dla n: Załóżmy, że istnieje taki dzień tygodnia t, że t jest środą oraz wszystkie dni poprzedzające t także wypadały w środę. Należy wykazać, że dzień t+1 także wypada w środę. Ponieważ wszystkie dni poprzedzające dzień t były środą, to był nią w szczególności dzień t-6 (dzień wypadający 6 dni przed dniem t). Dzień t-6 był dokładnie tydzień przed dniem t+1, a ponieważ dni tygodnia powtarzają się cyklicznie co siedem, to dnia t+1 także była środa. ∎

[edytuj] Wszystkie psy są białe

Udowodnimy teraz, że wszystkie psy są białe.

Baza: Na obrazku po prawej stronie
Krok indukcyjny dla n: Załóżmy, że dla wszystkich co najwyżej n-elementowych zbiorów psów twierdzenie jest prawdziwe. Rozważmy teraz n+1 elementowy zbiór psów, w którym wyróżnimy jednego psa. Nazwijmy go Azor.

Załóżmy teraz nie wprost, że Azor nie jest biały. Zbiór składający się z wszystkich psów poza Azorem jest z założenia indukcyjnego zbiorem psów maści białej. Wyróżnijmy teraz innego psa, Pimpka i rozważmy zbiór składający się z Azora i pozostałych psów z wyłączeniem Pimpka. Ten zbiór także z założenia indukcyjnego składa się z psów maści białej, a więc wbrew założeniu Azor jest biały. Dochodzimy do sprzeczności przez założenie, że w zbiorze n+1 psów znajduje się pies niebiały. ∎

[edytuj] Suma ciągu arytmetycznego

Udowodnimy teraz wzór na sumę skończoną ciągu arytmetycznego

Baza

Po podstawieniu za n liczby 2 otrzymamy

wartość ta z definicji ciągu arytmetycznego jest równa

Krok indukcyjny dla n

Korzystając z bazy indukcji udowodnimy, że twierdzenie jest prawdziwe dla n+1. Ponieważ w bazie indukcji braliśmy n=2, w kroku indukcyjnym musi wykazać, że twierdzenie jest prawdziwe dla n+1=3