Indukcja matematyczna

Indukcja matematyczna – metoda:

• dowodzenia twierdzeń o prawdziwości nieskończonej liczby zdań (tez);
• definiowania rekurencyjnego, zob. osobna sekcja.

W najbardziej typowych przypadkach dotyczą one liczb naturalnych, choć metodę indukcji stosuje się też do innych zbiorów dobrze uporządkowanych – ten typ indukcji matematycznej jest znany jako indukcja pozaskończona. Dowody indukcyjne to wbrew nazwie rozumowania nie indukcyjne, lecz dedukcyjne, podobnie jak cała matematykaSzablon:Fakt.

Indukcję wykorzystuje się w dowodach między innymi tożsamości, nierówności oraz innych twierdzeń jak reguła znaków Kartezjusza. Najstarsza znana argumentacja tego typu dotyczy sumy początkowych liczb nieparzystych; podał go Francesco Maurolico w pracy Arithmeticorum libri duo (Dwie księgi o arytmetyce) z 1575 roku.

Wprowadzenie

Efekt domina

Jak dowieść prawdziwości poniższych stwierdzeń?

$\begin{array}{cc}{2}^n⩾n& \mathrm{d}\mathrm{l}\mathrm{a}\mathrm{w}\mathrm{s}\mathrm{z}\mathrm{y}\mathrm{s}\mathrm{t}\mathrm{k}\mathrm{i}\mathrm{c}\mathrm{h}n\in \mathbb{N},\\ 1+2+\dots +n=\frac{n(n+1)}{2}& \mathrm{d}\mathrm{l}\mathrm{a}\mathrm{w}\mathrm{s}\mathrm{z}\mathrm{y}\mathrm{s}\mathrm{t}\mathrm{k}\mathrm{i}\mathrm{c}\mathrm{h}n\in \mathbb{N},\\ n^{n+1}⩾(n+1{)}^n& \mathrm{d}\mathrm{l}\mathrm{a}\mathrm{w}\mathrm{s}\mathrm{z}\mathrm{y}\mathrm{s}\mathrm{t}\mathrm{k}\mathrm{i}\mathrm{c}\mathrm{h}n\in \mathbb{N}\mathrm{p}\mathrm{o}\mathrm{z}\mathrm{a}n=1,2.\end{array}$

Każde z nich zawiera zmienną $n$ przebiegającą zbiór nieskończony $\mathbb{N}.$ Każde z tych stwierdzeń jest w istocie zbiorem nieskończenie wielu stwierdzeń. Można zbadać skończoną ich liczbę, gdzie $n$ przyjmuje pewne konkretne wartości, przykładowo sprawdzić $2^n⩾n$ dla $n=1,2,3,\dots ,1000000,$ ale nie jest to dowodem. Z drugiej strony nie sposób sprawdzić prawdziwości nieskończenie wielu stwierdzeń w skończonym czasie. Pozostaje więc uciec się do innych metod. Mając na celu dowodzenie stwierdzeń o wszystkich liczbach naturalnych wprowadza się aksjomat – jest to w istocie piąty z aksjomatów Giuseppe Peana (1858–1932) liczb naturalnych – tzw. aksjomat indukcji matematycznej (zob. szczegóły).

Często używaną ilustracją jest efekt domina: ustawiając szereg kamieni domina jeden za drugim można być pewnym przewrócenia wszystkich kamieni (nawet ich nieskończonej liczby), jeśli tylko przewrócono pierwszy kamień, a każdy kamień (z wyjątkiem ostatniego, o ile taki istnieje) przewraca kolejny.

Indukcja niezupełna

Aksjomat indukcji matematycznej

Jeśli $S$ jest podzbiorem $\mathbb{N},$ który spełnia

• $1\in S,$
• dla wszystkich $k\in \mathbb{N},$ jeśli $k\in S,$ to $k+1\in S,$

to $S$ stanowi całość $\mathbb{N},$ tzn. $S=\mathbb{N}.$

Aksjomat ten można wykorzystać do dowodzenia stwierdzeń postaci „$p_n$ dla każdego $n\in \mathbb{N}$” jak następuje. Niech $S\subseteq \mathbb{N}$ będzie zbiorem wszystkich liczb naturalnych, dla których $p_n$ jest prawdziwe. W pierwszym kroku, tzw. bazie indukcji, sprawdza się, czy $1\in S,$ czyli prawdziwość $p_1.$ Następnie zakłada się, że $k\in S,$ czyli prawdziwość $p_k,$ i przy tym założeniu, nazywanym hipotezą indukcyjną, dowodzi się prawdziwości $p_{k+1}.$ W ten sposób pokazuje się, że $k\in S$ pociąga $k+1\in S.$ Z aksjomatu indukcji matematycznej wynika $S=\mathbb{N},$ a więc $p_n$ jest prawdziwe dla wszystkich $n\in \mathbb{N}.$

Powyższy aksjomat można więc sformułować w postaci następującej procedury:

Zasada indukcji matematycznej

Niech $p_n$ będzie stwierdzeniem zawierającym liczbę naturalną $n$. Można dowieść stwierdzenia

dla każdego $n\in \mathbb{N}$ jest $p_n,$

zapewniając, że

• $p_1$ jest prawdziwe,
• dla wszystkich $k\in \mathbb{N},$ jeśli $p_k$ jest prawdziwe, to $p_{k+1}$ jest prawdziwe.

Dowody korzystające z zasady indukcji matematycznej składają się z dwóch kroków. Pierwszym jest dowód prawdziwości $p_1;$ w praktyce jest to zwykle dość proste, ale nie wolno zaniedbywać tego kroku. W drugim kroku zakłada się prawdziwość $p_k,$ założenie to jest hipotezą indukcyjną, i pod tym założeniem dowodzi prawdziwości $p_{k+1}.$ Dowód przez indukcję nie będzie pełny (ani poprawny), jeśli przeprowadzi się tylko pierwszy krok, a pominie drugi bądź wykona drugi z kroków, a opuści pierwszy. Kontrastując z opisanym dalej wariantem powyższą zasadę nazywa się też indukcją niezupełną.

Przykłady

Suma początkowych liczb naturalnych

Szablon:Zobacz też

Należy dowieść

$1+2+\dots +n=\frac{n(n+1)}{2}\mathrm{d}\mathrm{l}\mathrm{a}\mathrm{w}\mathrm{s}\mathrm{z}\mathrm{y}\mathrm{s}\mathrm{t}\mathrm{k}\mathrm{i}\mathrm{c}\mathrm{h}n\in \mathbb{N}.$

W tym celu wykorzystana zostanie zasada indukcji matematycznej:

• $1=\frac{1(1+1)}{2},$ a więc wzór jest prawdziwy dla $n=1.$
• Czyniąc założenie (hipotezę indukcyjną) $1+2+\dots +k=\frac{k(k+1)}{2}$ należy upewnić się, że $1+2+\dots +k+(k+1)=\frac{(k+1)((k+1)+1)}{2}.$

Otóż

$\begin{array}{cc}1+2+\dots +k+(k+1)& =\frac{k(k+1)}{2}+(k+1)\mathrm{(}\mathrm{h}\mathrm{i}\mathrm{p}\mathrm{o}\mathrm{t}\mathrm{e}\mathrm{z}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{.}\mathrm{)}\\ & =(\frac{k}{2}+1)(k+1)\\ & =\frac{(k+1)(k+2)}{2},\end{array},$

a więc wzór jest prawdziwy dla $n=k+1,$ o ile tylko jest prawdziwy dla $n=k.$

Na mocy zasady indukcji matematycznej

$1+2+\dots +n=\frac{n(n+1)}{2}\mathrm{d}\mathrm{l}\mathrm{a}\mathrm{w}\mathrm{s}\mathrm{z}\mathrm{y}\mathrm{s}\mathrm{t}\mathrm{k}\mathrm{i}\mathrm{c}\mathrm{h}n\in \mathbb{N}.$

Suma początkowych potęg dwójki

Szablon:Zobacz też

Należy dowieść

$2^1+2^2+2^3+\dots +2^n=2^{n+1}-2\mathrm{d}\mathrm{l}\mathrm{a}\mathrm{w}\mathrm{s}\mathrm{z}\mathrm{y}\mathrm{s}\mathrm{t}\mathrm{k}\mathrm{i}\mathrm{c}\mathrm{h}n\in \mathbb{N}.$

• Jest $2^1=2^{1+1}-2,$ co dowodzi prawdziwości stwierdzenia dla $n=1.$
• Zakładając $2+2^2+2^3+\dots +2^k=2^{k+1}-2$ należy dowieść $2^1+2^2+2^3+\dots +2^k+2^{k+1}=2^{(k+1)+1}-2.$

Ponieważ

$\begin{array}{cc}{2}^1+2^2+2^3+\dots +2^k+2^{k+1}& =(2^{k+1}-2)+2^{k+1}\mathrm{(}\mathrm{h}\mathrm{i}\mathrm{p}\mathrm{o}\mathrm{t}\mathrm{e}\mathrm{z}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{.}\mathrm{)}\\ & =2(2^{k+1})-2\\ & =2^{k+2}-2,\end{array}$

to wzór jest prawdziwy dla $n=k+1,$ jeśli tylko jest prawdziwy dla $n=k.$

Zatem

$2^1+2^2+2^3+\dots +2^n=2^{n+1}-2\mathrm{d}\mathrm{l}\mathrm{a}\mathrm{w}\mathrm{s}\mathrm{z}\mathrm{y}\mathrm{s}\mathrm{t}\mathrm{k}\mathrm{i}\mathrm{c}\mathrm{h}n\in \mathbb{N}.$

Nierówność Bernoulliego

Szablon:Zobacz też

Niech $h⩾-1$ będzie ustaloną liczbą rzeczywistą. Należy udowodnić, że $(1+h{)}^n⩾1+nh$ dla wszystkich $n\in \mathbb{N}.$

• Skoro $(1+h{)}^1⩾1+1h,$ to nierówność jest prawdziwa dla $n=1.$
• Przyjmując $(1+h{)}^k⩾1+kh$ wykazana zostanie $(1+h{)}^{k+1}⩾1+(k+1)h.$

Zachodzi

$\begin{array}{cc}(1+h{)}^{k+1}& =(1+h{)}^k(1+h)\\ & ⩾(1+kh)(1+h)\mathrm{(}\mathrm{h}\mathrm{i}\mathrm{p}\mathrm{.}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{.}\mathrm{i}1+h⩾0\mathrm{)}\\ & =1+h+kh+k{h}^2\\ & ⩾1+h+kh+0\\ & =1+(k+1)h,\end{array}$

więc nierówność jest prawdziwa dla $n=k+1,$ o ile jest prawdziwa dla $n=k.$

Stąd

$(1+h{)}^n⩾1+nh\mathrm{d}\mathrm{l}\mathrm{a}\mathrm{w}\mathrm{s}\mathrm{z}\mathrm{y}\mathrm{s}\mathrm{t}\mathrm{k}\mathrm{i}\mathrm{c}\mathrm{h}n\in \mathbb{N}(\mathrm{o}\mathrm{r}\mathrm{a}\mathrm{z}h⩾-1).$

Indukcja zupełna

Czasami wygodnie jest użyć zasady indukcji w nieco innej postaci. Zakłada się w niej prawdziwość nie tylko $q_k,$ ale każdego ze zdań $q_1,q_2,\dots ,q_k$ i wnosi o prawdziwości $q_{k+1}.$ Zapewnia to o prawdziwości $q_n$ dla wszystkich $n\in \mathbb{N},$ o czym mówi poniższy

Lemat

Niech $q_n$ będzie stwierdzeniem zawierającym liczbę naturalną $n$. Zakładając, że

• $q_1$ jest prawdziwe,
• dla wszystkich $k\in \mathbb{N},$ jeśli $q_1,q_2,\dots ,q_k$ są prawdziwe, to $q_{k+1}$ jest prawdziwe,

otrzymuje się prawdziwość $q_n$ dla wszystkich $n\in \mathbb{N}$.

Dzięki niemu zasada indukcji matematycznej może zyskać nową, czasem bardziej użyteczną postać, tzw. indukcji zupełnej.

Zasada indukcji matematycznej

Niech $q_n$ będzie stwierdzeniem zawierającym liczbę naturalną $n$. Można dowieść stwierdzenia

dla każdego $n\in \mathbb{N}$ jest $q_n,$

zapewniając, że

• $q_1$ jest prawdziwe,
• dla wszystkich $k\in \mathbb{N},$ jeśli $q_1,q_2,\dots ,q_k$ są prawdziwe, to $q_{k+1}$ jest prawdziwe.

Inne warianty

Indukcja z dowolną bazą

Stwierdzenie „$2^n⩾n^2$” nie jest prawdziwe dla wszystkich liczb naturalnych $n,$ zachodzi jednak dla wszystkich liczb naturalnych $n⩾4.$ Do dowiedzenia tego i podobnych mu stwierdzeń również można wykorzystać zasadę indukcji matematycznej. Niech $a$ będzie ustaloną liczbą całkowitą (dodatnią, ujemną, zerem) i niech $p_n$ będzie stwierdzeniem dotyczącym liczby całkowitej $n⩾a.$ Udowodnienie prawdziwości $p_n$ dla $n⩾a$ polega na wykazaniu, że

• $p_a$ jest prawdziwe,
• dla wszystkich $k⩾a,$ jeśli $p_k$ jest prawdziwe, to $p_{k+1}$ jest prawdziwe.

Istnieje również podobna modyfikacja zasady indukcji zupełnej.

Indukcja wsteczna

Szablon:Zobacz też

Niech $r_n$ oznacza pewne stwierdzenie dotyczące liczby naturalnej $n$. Jeżeli

• istnieje ściśle rosnący ciąg liczb naturalnych $\{n_k\},$ dla którego $r_{n_k}$ jest prawdziwe dla wszystkich $k\in \mathbb{N},$
• dla wszystkich $m\in \mathbb{N},$ jeśli $r_{m+1}$ jest prawdziwe, to $r_m$ jest prawdziwe,

to $r_n$ jest prawdziwe dla wszystkich $n\in \mathbb{N}.$

Aksjomat czy twierdzenie?

Szablon:Osobny artykuł W wielu źródłach można zamiast „aksjomatu indukcji” spotkać nazwę „twierdzenie o indukcji”; odpowiedź na pytanie tytułowe zależy od kontekstu, w którym jest ono stawiane.

W zastosowaniach matematyki, matematyce elementarnej, czy matematyce dyskretnej dominuje tendencja do mówienia o „twierdzeniu o indukcji matematycznej”, również dlatego, by uniknąć przesadnej formalizacji. Wprowadzając indukcję matematyczną podaje się często dowód twierdzenia o indukcji korzystając z dość intuicyjnej zasady dobrego uporządkowania liczb naturalnych, tzn. założenia, że każdy niepusty zbiór liczb naturalnych zawiera element najmniejszy.

Natomiast w logice, szczególnie gdy liczby naturalne wprowadzane są za pomocą aksjomatów Peana, indukcja traktowana jest jako aksjomat. Z powodu kwantyfikowania po zbiorach w gruncie rzeczy jest to aksjomat logiki drugiego rzędu; w przypadku, gdy rozwijana teoria jest formalizowana w logice pierwszego rzędu, słowo „aksjomat” w wyrażeniu „aksjomat indukcji” należy rozumieć w istocie jako schemat aksjomatu: nieskończoną listę aksjomatów, osobnych dla każdej formuły.

Definiowanie

Szablon:Osobny artykuł Ważną konsekwencją zasady indukcji matematycznej jest następujące twierdzenie uzasadniające poprawność definiowania rekurencyjnego:

Niech $U$ będzie zbiorem wszystkich ciągów skończonych o wyrazach z niepustego zbioru $X,$ a ${\mathbb{N}}_{<n}=\{m\in \mathbb{N}:m<n\}$ oznacza zbiór liczb naturalnych mniejszych od wybranej liczby $n\in \mathbb{N}.$ Dla danej funkcji $f:U\to X$ istnieje jedna i tylko jedna funkcja $g:\mathbb{N}\to X,$ która dla każdej liczby naturalnej $k\in \mathbb{N}$ spełnia

$g(k)=f\left(g{\upharpoonright }_{{\mathbb{N}}_{<k}}\right),$

gdzie $\upharpoonright$ oznacza zawężenie funkcji.

Zobacz też

• indukcja strukturalna
• paradoks koni – przykład błędnego użycia indukcji matematycznej
• zbiór induktywny

Linki zewnętrzne

• Szablon:Otwarty dostęp Szablon:Cytuj stronę
• Szablon:Otwarty dostęp Szablon:Cytuj stronę
• Szablon:Pismo Delta
• Szablon:Otwarty dostęp Szablon:Cytuj stronę