Indukcja matematyczna

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, podał Francesco Maurolico (1494–1575) w pracy Arithmeticorum libri duo (Dwie księgi o arytmetyce) z 1575 roku. Od tego czasu indukcję wykorzystano w dowodach szeregu tożsamości, nierówności oraz innych twierdzeń jak reguła znaków Kartezjusza.

Wprowadzenie 

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

Każde z nich zawiera zmienną  przebiegającą zbiór nieskończony  Każde z tych stwierdzeń jest w istocie zbiorem nieskończenie wielu stwierdzeń. Można zbadać skończoną ich liczbę, gdzie  przyjmuje pewne konkretne wartości, przykładowo sprawdzić  dla  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  jest podzbiorem  który spełnia
 
 dla wszystkich  jeśli  to 
 to  stanowi całość  tzn. 

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

Powyższy aksjomat można więc sformułować w postaci następującej procedury:
 Zasada indukcji matematycznej
 Niech  będzie stwierdzeniem zawierającym liczbę naturalną . Można dowieść stwierdzenia
 dla każdego  jest 
 zapewniając, że
  jest prawdziwe,
 dla wszystkich  jeśli  jest prawdziwe, to  jest prawdziwe.

Dowody korzystające z zasady indukcji matematycznej składają się z dwóch kroków. Pierwszym jest dowód prawdziwości  w praktyce jest to zwykle dość proste, ale nie wolno zaniedbywać tego kroku. W drugim kroku zakłada się prawdziwość  założenie to jest hipotezą indukcyjną, i pod tym założeniem dowodzi prawdziwości  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ść
 
 W tym celu wykorzystana zostanie zasada indukcji matematycznej:
  a więc wzór jest prawdziwy dla 
 Czyniąc założenie (hipotezę indukcyjną)  należy upewnić się, że 
 Otóż
 
 a więc wzór jest prawdziwy dla  o ile tylko jest prawdziwy dla 

 Na mocy zasady indukcji matematycznej
 

 Suma początkowych potęg dwójki
 
 Należy dowieść
 
 Jest  co dowodzi prawdziwości stwierdzenia dla 
 Zakładając  należy dowieść 
 Ponieważ
 
 to wzór jest prawdziwy dla  jeśli tylko jest prawdziwy dla 

 Zatem
 

 Nierówność Bernoulliego
 
 Niech  będzie ustaloną liczbą rzeczywistą. Należy udowodnić, że  dla wszystkich 
 Skoro  to nierówność jest prawdziwa dla 
 Przyjmując  wykazana zostanie 
 Zachodzi
 
 więc nierówność jest prawdziwa dla  o ile jest prawdziwa dla 

 Stąd

Indukcja zupełna 
Czasami wygodnie jest użyć zasady indukcji w nieco innej postaci. Zakłada się w niej prawdziwość nie tylko  ale każdego ze zdań  i wnosi o prawdziwości  Zapewnia to o prawdziwości  dla wszystkich  o czym mówi poniższy
 Lemat
 Niech  będzie stwierdzeniem zawierającym liczbę naturalną . Zakładając, że
  jest prawdziwe,
 dla wszystkich  jeśli  są prawdziwe, to  jest prawdziwe,
 otrzymuje się prawdziwość  dla wszystkich .

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

 Zasada indukcji matematycznej
 Niech  będzie stwierdzeniem zawierającym liczbę naturalną . Można dowieść stwierdzenia
 dla każdego  jest 
 zapewniając, że
  jest prawdziwe,
 dla wszystkich  jeśli  są prawdziwe, to  jest prawdziwe.

Inne warianty 
 Indukcja z dowolną bazą
 Stwierdzenie „” nie jest prawdziwe dla wszystkich liczb naturalnych  zachodzi jednak dla wszystkich liczb naturalnych  Do dowiedzenia tego i podobnych mu stwierdzeń również można wykorzystać zasadę indukcji matematycznej. Niech  będzie ustaloną liczbą całkowitą (dodatnią, ujemną, zerem) i niech  będzie stwierdzeniem dotyczącym liczby całkowitej  Udowodnienie prawdziwości  dla  polega na wykazaniu, że
  jest prawdziwe,
 dla wszystkich  jeśli  jest prawdziwe, to  jest prawdziwe.

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

 Indukcja wsteczna
 
 Niech  oznacza pewne stwierdzenie dotyczące liczby naturalnej . Jeżeli
 istnieje ściśle rosnący ciąg liczb naturalnych  dla którego  jest prawdziwe dla wszystkich 
 dla wszystkich  jeśli  jest prawdziwe, to  jest prawdziwe,
 to  jest prawdziwe dla wszystkich

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  będzie zbiorem wszystkich ciągów skończonych o wyrazach z niepustego zbioru  a  oznacza zbiór liczb naturalnych mniejszych od wybranej liczby  Dla danej funkcji  istnieje jedna i tylko jedna funkcja  która dla każdej liczby naturalnej  spełnia
 
 gdzie  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

Linki zewnętrzne