Indukcja matematyczna

Z Nonsensopedii, polskiej encyklopedii humoru
Medal.svg
Przybornik do przeprowadzania dowodów indukcyjnych
Wystarczy tylko pchnąć...

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.

Schemat ogólny[edytuj • edytuj kod]

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.

Historia wynalazku indukcji matematycznej[edytuj • edytuj kod]

Cewka indukcyjna 110V (u góry) oraz 220V (u dołu)

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]

Indukcja niezupełna[edytuj • edytuj kod]

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.

Indukcja matematyczna a teoria gry w domino[edytuj • edytuj kod]

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.

Przykłady wykorzystania[edytuj • edytuj kod]

Parzystość wszystkich liczb[edytuj • edytuj kod]

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 n1 + n2, gdzie n1, n2<n. Ponieważ zgodnie z założeniem indukcyjnym n1 i n2 są parzyste, to ich suma też jest liczbą parzystą. A więc n jest liczbą parzystą. ∎

Nieparzystość wszystkich liczb[edytuj • edytuj kod]

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 n1 + n2 + 1, gdzie n1, n2<n. Ponieważ zgodnie z założeniem indukcyjnym n1 i n2 są nieparzyste, to ich suma plus 1 jest liczbą nieparzystą. A więc n jest liczbą nieparzystą. ∎

Wieczna środa[edytuj • edytuj kod]

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. ∎

Wszystkie psy są białe[edytuj • edytuj kod]

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

Dogoarg2.jpg
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. ∎

Suma ciągu arytmetycznego[edytuj • edytuj kod]

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, czyli n=3:
a z definicji ciągu arytmetycznego
Złożenie ostatnich dwóch równości daje nam układ tautologiczny. Tym samym udowodniliśmy, że dowodzone twierdzenie jest tautologią. ∎