Indukcja matematyczna

Ten artykuł dotyczy dziedziny matematyki. Zobacz też Indukcja.

Indukcja matematyczna

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

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

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

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

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

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

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

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

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

Suma ciągu arytmetycznego

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

$S_{n}=a_{1}+a_{2}+\dots +a_{n}={\frac {a_{1}+a_{n}}{2}}n$

Baza

Po podstawieniu za n liczby 2 otrzymamy

$S_{2}=a_{1}+a_{2}$

wartość ta z definicji ciągu arytmetycznego jest równa ${\frac {a_{1}+a_{2}}{2}}2=a_{1}+a_{2}$

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:

$S_{3}=a_{1}+a_{2}+a_{3}$

$S_{3}=S_{2}+a_{3}$

a z definicji ciągu arytmetycznego

$S_{2}=S_{3}-a_{3}$

Złożenie ostatnich dwóch równości daje nam układ tautologiczny. Tym samym udowodniliśmy, że dowodzone twierdzenie jest tautologią. ∎