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^[1], choć metodę indukcji stosuje się też do innych zbiorów dobrze uporządkowanych – ten typ indukcji matematycznej jest znany jako indukcja pozaskończona^[1]. 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^[2]. Najstarsza znana argumentacja tego typu dotyczy sumy początkowych liczb nieparzystych^{[uwaga 1]}; podał go Francesco Maurolico w pracy Arithmeticorum libri duo (Dwie księgi o arytmetyce) z 1575 roku^[3].

Wprowadzenie

Efekt domina

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

${\displaystyle {\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ą ${\displaystyle n}$ przebiegającą zbiór nieskończony ${\displaystyle \mathbb {N} .}$ Każde z tych stwierdzeń jest w istocie zbiorem nieskończenie wielu stwierdzeń. Można zbadać skończoną ich liczbę, gdzie ${\displaystyle n}$ przyjmuje pewne konkretne wartości, przykładowo sprawdzić ${\displaystyle 2^{n}\geqslant n}$ dla ${\displaystyle n=1,2,3,\dots ,1\,000\,000,}$ ale nie jest to dowodem^{[uwaga 2]}. 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 ${\displaystyle S}$ jest podzbiorem ${\displaystyle \mathbb {N} ,}$ który spełnia

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

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

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

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

Zasada indukcji matematycznej

Niech ${\displaystyle p_{n}}$ będzie stwierdzeniem zawierającym liczbę naturalną ${\displaystyle n}$^{[uwaga 3]}. Można dowieść stwierdzenia

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

zapewniając, że

• ${\displaystyle p_{1}}$ jest prawdziwe,
• dla wszystkich ${\displaystyle k\in \mathbb {N} ,}$ jeśli ${\displaystyle p_{k}}$ jest prawdziwe, to ${\displaystyle 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 ${\displaystyle p_{1};}$ w praktyce jest to zwykle dość proste, ale nie wolno zaniedbywać tego kroku. W drugim kroku zakłada się prawdziwość ${\displaystyle p_{k},}$ założenie to jest hipotezą indukcyjną, i pod tym założeniem dowodzi prawdziwości ${\displaystyle 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ść

${\displaystyle 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:

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

Otóż

${\displaystyle {\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 ${\displaystyle n=k+1,}$ o ile tylko jest prawdziwy dla ${\displaystyle n=k.}$

Na mocy zasady indukcji matematycznej

${\displaystyle 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ść

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

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

Ponieważ

${\displaystyle {\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 ${\displaystyle n=k+1,}$ jeśli tylko jest prawdziwy dla ${\displaystyle n=k.}$

Zatem

${\displaystyle 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 ${\displaystyle h\geqslant -1}$ będzie ustaloną liczbą rzeczywistą. Należy udowodnić, że ${\displaystyle (1+h)^{n}\geqslant 1+nh}$ dla wszystkich ${\displaystyle n\in \mathbb {N} .}$

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

Zachodzi

${\displaystyle {\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 ${\displaystyle n=k+1,}$ o ile jest prawdziwa dla ${\displaystyle n=k.}$

Stąd

${\displaystyle (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 ${\displaystyle q_{k},}$ ale każdego ze zdań ${\displaystyle q_{1},q_{2},\dots ,q_{k}}$ i wnosi o prawdziwości ${\displaystyle q_{k+1}.}$ Zapewnia to o prawdziwości ${\displaystyle q_{n}}$ dla wszystkich ${\displaystyle n\in \mathbb {N} ,}$ o czym mówi poniższy

Lemat

Niech ${\displaystyle q_{n}}$ będzie stwierdzeniem zawierającym liczbę naturalną ${\displaystyle n}$^{[uwaga 3]}. Zakładając, że

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

otrzymuje się prawdziwość ${\displaystyle q_{n}}$ dla wszystkich ${\displaystyle n\in \mathbb {N} }$^{[uwaga 4]}.

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

Zasada indukcji matematycznej

Niech ${\displaystyle q_{n}}$ będzie stwierdzeniem zawierającym liczbę naturalną ${\displaystyle n}$^{[uwaga 3]}. Można dowieść stwierdzenia

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

zapewniając, że

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

Inne warianty

Indukcja z dowolną bazą

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

• ${\displaystyle p_{a}}$ jest prawdziwe,
• dla wszystkich ${\displaystyle k\geqslant a,}$ jeśli ${\displaystyle p_{k}}$ jest prawdziwe, to ${\displaystyle p_{k+1}}$ jest prawdziwe^{[uwaga 5]}.

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

Indukcja wsteczna

Niech ${\displaystyle r_{n}}$ oznacza pewne stwierdzenie dotyczące liczby naturalnej ${\displaystyle n}$^{[uwaga 3]}. Jeżeli

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

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

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

gdzie ${\displaystyle \upharpoonright }$ oznacza zawężenie funkcji.

Zobacz też

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

Uwagi

Przypisy

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