Indukcja matematyczna

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

W matematyce, termin indukcja matematyczna używany jest na określenie szczególnej metody dowodzenia twierdzeń (w najbardziej typowych przypadkach o liczbach naturalnych) ale także jest on używany na oznaczenie konstrukcji pewnych obiektów.

Wbrew nazwie, argumenty oparte na indukcji matematycznej nie są rozumowaniami indukcyjnymi, lecz dedukcyjnymi. Najstarszy znany dowód indukcyjny był podany przez Francesco Maurolico w pracy Arithmeticorum libri fuo w 1575. Maurolico udowodnił przez indukcję, że suma pierwszych n nieparzystych liczb naturalnych wynosi $n 2$ .

[edytuj] Intuicje

Kamienie domina

Zarówno definicje indukcyjne jak i twierdzenie o indukcji matematycznej można porównać do rozumowań krok po kroku, gdzie kroki są ponumerowane liczbami naturalnymi. Sedno dowodów indukcyjnych leży zawsze w podaniu uzasadnienia, że na pierwszym kroku wszystko jest dobrze oraz że dla każdego $n\in {\mathbb N}$ , jeśli na kroku n wszystko było dobrze, to stąd można wywnioskować że na kroku n+1 też wszystko jest dobrze. Często używaną ilustracją dla tego typu argumentacji jest efekt domina. Wyobraźmy sobie że ustawiliśmy szereg kamieni używanych do gry w domino tak że stoją one jeden za drugim na krótszym boku. Przypuścmy, że przed opuszczeniem pomieszczenia z tymi kamieniami upewniliśmy się, że przewrócenie któregokolwiek z nich powoduje upadek następnego. Jakiś czas po wyjściu z pokoju dostajemy informację że ktoś przewrócił pierwszy kamień. Możemy wtedy natychmiast stwierdzić, że wszystkie kamienie się przewróciły.

[edytuj] Twierdzenie o indukcji matematycznej

Następujące twierdzenia są natychmiastową konsekwencją bardzo intuicyjnej własności liczb naturalnych, stwierdzającej że w każdym niepustym zbiorze liczb naturalnych jest liczba najmniejsza.

[edytuj] Zasada indukcji matematycznej

Jeśli $T (n)$ oznacza pewne twierdenie mówiące o liczbach naturalnych $n$ , to aby udowodnić, że twierdzenie to jest prawdziwe dla każdej liczby naturalnej $n$ nie mniejszej od $n 0$ (samo $n 0$ może być równe $1$ albo być inną ustaloną liczbą naturalną), wystarczy:

dowieść, że jest ono prawdziwe dla liczby $n 0$ , to znaczy sprawdzić, że zachodzi $T (n 0)$ .
dla każdej liczby naturalnej $n$ nie mniejszej od $n 0$ , wychodząc z założenia, że twierdzenie to jest prawdziwe dla liczby $n$ , wyprowadzić, że jest ono prawdziwe dla $n + 1$ , chodzi bowiem o to, aby wykazać, że dla każdej liczby naturalnej $n$ nie mnejszej od $n 0$ prawdziwa jest implikacja: $T(n) \implies T(n+1)$

[edytuj] Wersja podstawowa

Przypuśćmy, że $P (n)$ jest pewnym wyrażeniem (czyli formułą w jakimś języku) w którym jedyną zmienną wolną jest $n$ i dziedzina tej zmiennej zawiera wszystkie liczby naturalne. Załóżmy, że

(a)

P (1)

jest zdaniem prawdziwym oraz

(b) dla każdego $n\in \mathbb N$ zachodzi implikacja

$P(n)\quad \implies \quad P(n+1)$ .

Wówczas $P (n)$ jest prawdziwe dla każdej liczby naturalnej $n\in \mathbb N$ .

[edytuj] Wariant zwany indukcją zupełną

Przypuśćmy, że $P (n)$ jest pewnym wyrażeniem, w którym jedyną zmienną wolną jest $n$ i dziedzina tej zmiennej zawiera wszystkie liczby naturalne. Załóżmy, że

$(\forall m<n)(P(m))\quad \implies \quad P(n)$ .

Wówczas $P (n)$ jest prawdziwe dla każdego $n\in \mathbb N$ .

[edytuj] Twierdzenie o definiowaniu indukcyjnym

Niech $A$ będzie niepustym zbiorem, zaś $U$ zbiorem wszystkich ciągów skończonych o wyrazach w $A$ . Przypuśćmy, że dana jest funkcja $f: U \to A$ . Wówczas istnieje dokładnie jedna funkcja $g: \mathbb N \to A$ taka, że dla każdej liczby naturalnej $n\in \mathbb N$ mamy