Otwórz menu główne
Disambug.svg Ten artykuł dotyczy dziedziny matematyki. Zobacz też Indukcja.
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.

Spis treści

Schemat ogólnyEdytuj

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 matematycznejEdytuj

 
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łnaEdytuj

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 dominoEdytuj

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 wykorzystaniaEdytuj

Parzystość wszystkich liczbEdytuj

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 liczbEdytuj

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 środaEdytuj

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łeEdytuj

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

Suma ciągu arytmetycznegoEdytuj

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