Edytujesz „Indukcja matematyczna”

{{sur|dziedziny matematyki|[[Indukcja]]}}
{{medal}}
[[Plik:Dominospiel.JPG|thumb|200px|Przybornik do przeprowadzania dowodów indukcyjnych]]
[[Plik:Domino Cascade.JPG|thumb|200px|Wystarczy tylko pchnąć...]]
{{T}}zabawka matematyczna, służąca do pokazywania prawdziwości różnych [[twierdzenie matematyczne|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 ==
[[Plik:Bricks2.jpg|thumb|200px|Cewka indukcyjna 110V (u góry) oraz 220V (u dołu)]]
Indukcja matematyczna została wynaleziona w [[Bell Labs|Laboratoriach Bella]] w okresie największego postępu elektryfikacji miast i wsi. Miała ona stanowić tani substytut [[Cewka|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 [[Inercja|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. {{fakt}} 

== 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 [[domino|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<sub>1</sub> + n<sub>2</sub>, gdzie n<sub>1</sub>, n<sub>2</sub><n. Ponieważ zgodnie z założeniem indukcyjnym n<sub>1</sub> i n<sub>2</sub> 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<sub>1</sub> + n<sub>2</sub> + 1, gdzie n<sub>1</sub>, n<sub>2</sub><n. Ponieważ zgodnie z założeniem indukcyjnym n<sub>1</sub> i n<sub>2</sub> 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. 

[[Plik:Dogoarg2.jpg|120px|right]]
;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ąg arytmetyczny|ciągu arytmetycznego]]
:<math>S_n = a_1+a_2+\dots+a_n=\frac{a_1 + a_n}{2}n</math>

;Baza 
:Po podstawieniu za n liczby 2 otrzymamy
:::<math>S_2 = a_1+a_2</math>
:wartość ta z definicji ciągu arytmetycznego jest równa <math>\frac{a_1 + a_2}{2}2 = a_1 + a_2</math>
;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:
::<math>S_3 = a_1+a_2+a_3</math>
::<math>S_3 = S_2 + a_3</math>
:a z definicji ciągu arytmetycznego 
::<math>S_2 = S_3 - a_3</math>
:Złożenie ostatnich dwóch równości daje nam układ tautologiczny. Tym samym udowodniliśmy, że dowodzone twierdzenie jest [[tautologia|tautologią]]. ∎

{{Matematyka}}
[[Kategoria:Logika]]
[[Kategoria:Filozofia]]