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

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{aligned}2^{n}\geqslant n&\quad \mathrm {dla\ wszystkich} \ n\in \mathbb {N} ,\\1+2+\ldots +n={\tfrac {n(n+1)}{2}}&\quad \mathrm {dla\ wszystkich} \ n\in \mathbb {N} ,\\n^{n+1}\geqslant (n+1)^{n}&\quad \mathrm {dla\ wszystkich} \ n\in \mathbb {N} \ \mathrm {poza} \ n=1,2.\end{aligned}}$

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}\geqslant n$ dla $n=1,2,3,\dots ,1\,000\,000,$ 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

Należy dowieść

$1+2+\ldots +n={\tfrac {n(n+1)}{2}}\quad \mathrm {dla\ wszystkich} \ n\in \mathbb {N} .$

W tym celu wykorzystana zostanie zasada indukcji matematycznej:

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

Otóż

${\begin{aligned}1+2+\ldots +k+(k+1)&={\tfrac {k(k+1)}{2}}+(k+1)\qquad \mathrm {(hipoteza\ ind{.})} \\&=({\tfrac {k}{2}}+1)(k+1)\\&={\tfrac {(k+1)(k+2)}{2}},\end{aligned}},$

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+\ldots +n={\tfrac {n(n+1)}{2}}\quad \mathrm {dla\ wszystkich} \ n\in \mathbb {N} .$

Suma początkowych potęg dwójki

Należy dowieść

$2^{1}+2^{2}+2^{3}+\ldots +2^{n}=2^{n+1}-2\quad \mathrm {dla\ wszystkich} \ 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}+\ldots +2^{k}=2^{k+1}-2$ należy dowieść $2^{1}+2^{2}+2^{3}+\ldots +2^{k}+2^{k+1}=2^{(k+1)+1}-2.$

Ponieważ

${\begin{aligned}2^{1}+2^{2}+2^{3}+\ldots +2^{k}+2^{k+1}&=(2^{k+1}-2)+2^{k+1}\qquad \mathrm {(hipoteza\ ind{.})} \\&=2(2^{k+1})-2\\&=2^{k+2}-2,\end{aligned}}$

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

Zatem

$2^{1}+2^{2}+2^{3}+\ldots +2^{n}=2^{n+1}-2\quad \mathrm {dla\ wszystkich} \ n\in \mathbb {N} .$

Nierówność Bernoulliego

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

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

Zachodzi

${\begin{aligned}(1+h)^{k+1}&=(1+h)^{k}(1+h)\\&\geqslant (1+kh)(1+h)\qquad \mathrm {(hip{.}\ ind{.}\ i\;} 1+h\geqslant 0\mathrm {)} \\&=1+h+kh+kh^{2}\\&\geqslant 1+h+kh+0\\&=1+(k+1)h,\end{aligned}}$

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

Stąd

$(1+h)^{n}\geqslant 1+nh\quad \mathrm {dla\ wszystkich} \ n\in \mathbb {N} \ \ (\mathrm {oraz} \ h\geqslant -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}\geqslant n^{2}$” nie jest prawdziwe dla wszystkich liczb naturalnych $n,$ zachodzi jednak dla wszystkich liczb naturalnych $n\geqslant 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\geqslant a.$ Udowodnienie prawdziwości $p_{n}$ dla $n\geqslant a$ polega na wykazaniu, że

• $p_{a}$ jest prawdziwe,
• dla wszystkich $k\geqslant a,$ jeśli $p_{k}$ jest prawdziwe, to $p_{k+1}$ jest prawdziwe.

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

Indukcja wsteczna

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?

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

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} \colon m<n\}$ oznacza zbiór liczb naturalnych mniejszych od wybranej liczby $n\in \mathbb {N} .$ Dla danej funkcji $f\colon U\to X$ istnieje jedna i tylko jedna funkcja $g\colon \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

• Indukcja matematyczna, Zintegrowana Platforma Edukacyjna, zpe.gov.pl [dostęp 2024-03-19].
• Indukcja – wprowadzenie, portal ucze-sie.pl, Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego, smurf.mimuw.edu.pl [dostęp 2024-03-19].
• MichałM. Miśkiewicz MichałM., Mały krok dla człowieka, wielki skok dla indukcji, [w:] pismo „Delta”, deltami.edu.pl, wrzesień 2023, ISSN 0137-3005 [dostęp 2023-12-10]  (pol.).
• Mathematical induction (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-03-19].