Indukcja matematyczna

Ten artykuł od 2021-01 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła, najlepiej w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Indukcja matematyczna – metoda dowodzenia twierdzeń o prawdziwości nieskończonej liczby stwierdzeń oraz definiowania rekurencyjnego (zob. osobna sekcja). W najbardziej typowych przypadkach dotyczą one liczb naturalnych.

Dowody wykorzystujące metodę indukcji nazywa się dowodami indukcyjnymi, choć wbrew sugestywnej nazwie argumenty oparte na indukcji matematycznej nie są rozumowaniami indukcyjnymi, lecz dedukcyjnymi (podobnie jak cała matematyka). Najstarszy znany dowód indukcyjny, dotyczący sumy początkowych liczb nieparzystych^[a], podał Francesco Maurolico (1494–1575) w pracy Arithmeticorum libri duo („Dwie księgi o arytmetyce”) z 1575 roku.

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+\dots +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^[b]. 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}$^[c]. 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+\dots +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+\dots +k={\tfrac {k(k+1)}{2}}}$ należy upewnić się, że ${\displaystyle 1+2+\dots +k+(k+1)={\tfrac {(k+1)((k+1)+1)}{2}}.}$

Otóż

${\displaystyle {\begin{aligned}1+2+\dots +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+\dots +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}+\dots +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}+\dots +2^{k}=2^{k+1}-2}$ należy dowieść ${\displaystyle 2^{1}+2^{2}+2^{3}+\dots +2^{k}+2^{k+1}=2^{(k+1)+1}-2.}$

Ponieważ

${\displaystyle {\begin{aligned}2^{1}+2^{2}+2^{3}+\dots +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}+\dots +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}$^[c]. 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} }$^[d].

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}$^[c]. 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^[e].

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

Indukcja wsteczna

Niech ${\displaystyle r_{n}}$ oznacza pewne stwierdzenie dotyczące liczby naturalnej ${\displaystyle n}$^[c]. 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 pozaskończona
• indukcja strukturalna
• paradoks koni – przykład błędnego użycia indukcji matematycznej
• zbiór induktywny

Uwagi