Indukcja matematyczna

Z Nonsensopedii, polskiej encyklopedii humoru

Skocz do: nawigacji, szukaj
Ujednoznacznienie Ten artykuł dotyczy dziedziny matematyki. Zobacz też Indukcja.
Dominospiel.JPG

Przybornik do przeprowadzania dowodów indukcyjnych

Domino Cascade.JPG

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.

[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

Bricks2.jpg

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]

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

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

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

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

[edytuj] 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ą. ∎

Medal.png

Nasze strony
Przyjaciele