Indukcja matematyczna
Indukcja polega na wyciąganiu ogólnych wniosków na podstawie skończenie wielu przypadków.
Przykładowo wielekroć obserwowaliśmy, \
e jabłko puszczone z pewnej wysokości spada. Newton
wywnioskował stąd ogólne prawo cią\
enia. Podobnie obserwując codzienne wschody słońca mo\
na po
pewnym czasie dojść do przekonania, \
e słońce zawsze wschodzi o świcie. Jak wiemy, w długim okresie
czasu nie będzie to jednak prawda. Zatem metoda indukcji jest zawodną metodą wnioskowania.
Podobnie w matematyce mo\
na obserwować, \
e pewne własności liczb naturalnych przysługują kolejno
liczbom Po sprawdzeniu wielu takich liczb pojawia sie pokusa, by metodą indukcji
przyjąć, \
e dana własność przysługuje wszystkim liczbom naturalnym. Droga ta prowadzić mo\
e na
manowce.
Przykład. Niech zaś dla
Ponadto niech , zaś dla
nawias kwadratowy oznacza tu część całkowitą liczby rzeczywistej. Wtedy dla oraz
W odró\
nieniu od zawodnej metody indukcji opisanej powy\
ej, indukcja matematyczna jest jak
najbardziej niezawodną metodą dowodzenia twierdzeń. Nazwa tej metody bierze się z pewnego
zewnętrznego podobieństwa do metody indukcji.
Indukcja matematyczna dotyczy własności liczb naturalnych. W rozdziale 11 podaliśmy, jak w teorii
mnogości definiuje się liczby naturalne. Przypomnijmy, \
e to zbiór pusty , zaś liczba to zbiór
. W teorii mnogości definiuje się zbiór liczb naturalnych jako najmniejszy zbiór taki, \
e
1. i
2. dla ka\
dego mamy .
Istnienie takiego zbioru przyjmuje się w teorii mnogości w zasadzie jako aksjomat. Z tej definicji
wynika natychmiast następująca zasada.
Twierdzenie 13..1 (Zasada indukcji matematycznej) Jeśli jest podzbiorem zbioru liczb naturalnych
takim, \
e
1. i
2. dla ka\
dego mamy te\
,
to wtedy jest zbiorem wszystkich liczb naturalnych.
Dowód. Jeśli spełnia warunki 1. i 2., to spełnia te\
warunki definiujące w teorii mnogości zbiór liczb
naturalnych, więc . Z zało\
enia jednak , więc .
Zasadę indukcji matematycznej formułuje się równie\
w nieco innej postaci, w której mo\
na ją stosować
bezpośrednio do dowodzenia twierdzeń. Mianowicie, dla ka\
dej funkcji zdaniowej , je\
eli
1. i
2. dla ka\
dego , pociąga ,
to wtedy
3.
dla ka\
dego mamy .
Zasada indukcji matematycznej w tej formie wynika z twierdzenia 13.1, gdy za przyjmiemy wykres
funkcji zdaniowej . Punkty 1. i 2. w tej zasadzie nazywamy krokami indukcyjnymi (w punkcie 1.
często pomijamy tę nazwę). Zdanie nazywamy tezą indukcyjną (tezą indukcyjną nazywa
się te\
samą funkcję zdaniową ). Formalnie zasadę indukcji matematycznej dla funkcji zdaniowej
mo\
emy zapisać w postaci zdania
Z zasady indukcji matematycznej wynika tak zwana zasada minimum.
Twierdzenie 13..2 (Zasada minimum) Ka\
dy niepusty podzbiór zbioru liczb naturalnych zawiera
element najmniejszy.
Dowód. Niech będzie niepustym podzbiorem i niech
Przypuśćmy nie wprost, \
e nie ma elementu najmniejszego. W szczególności (bo jest
najmniejszą liczbą naturalną), więc .
Przypuśćmy teraz, \
e . Znaczy to, \
e jest rozłączny z . Jeśli teraz , to
byłaby najmniejszą liczbą w , sprzeczność. Dostajemy więc , czyli równie\

 i .
W ten sposób widzimy, \
e zbiór spełnia zało\
enia twierdzenia 13.1. Dlatego wnioskujemy, \
e .
Znaczy to jednak, \
e , sprzeczność.
Przykład. Udowodnimy metodą indukcji matematycznej nierówność Bernoulliego: dla i
mamy .
Nasza teza indukcyjna to
Zatem to funkcja zdaniowa .
1. Przypadek (sprawdzamy, \
e ). Niech .
, więc zachodzi.
2. Krok indukcyjny. Przypuśćmy , \
e zachodzi . Udowodnimy
, tzn. .
Niech więc . Na mocy zało\
enia indukcyjnego, . Dlatego mamy
co kończy dowód kroku indukcyjnego.
Z zasady indukcji matematycznej wnioskujemy, \
e teza indukcyjna zachodzi dla wszystkich .
Stosuje się te\
ró\
ne warianty zasady indukcji matematycznej.
Indukcja od miejsca .
Dowód. Wprowadzamy nową funkcję zdaniową wzorem
Wtedy zdanie jest równowa\
ne zdaniu
które wynika z zasady indukcji matematycznej.
Zasada indukcji porządkowej.
Przed dowodem zwróćmy uwagę, \
e ta forma indukcji ma tylko jeden krok indukcyjny:
Jednak dla zdanie to mówi, \
e
Poprzednik tej implikacji, czyli zdanie
jest prawdziwy (bo dla ka\
dego jest fałszem), więc z wynika w szczególności, \
e
jest prawdą. Zatem ``pierwszy krok'' indukcji jest tu jakby ukryty.
Dowód . Dowód przeprowadzimy przy u\
yciu zasady minimum. Przypuśćmy nie wprost, \
e
zachodzi, jednak zbiór jest niepusty. Niech będzie jego najmniejszym
elementem. Wówczas prawdą jest, \
e . Stosując dla dostajemy, \
e ,
czyli , sprzeczność.
Przykład. Udowodnimy, \
e liczba przekątnych -kąta wypukłego jest równa .
Niech oznacza funkcję zdaniową: `` liczba przekątnych -kąta wypukłego jest równa
''. Wówczas nasza teza indukcyjna ma postać .
1. Sprawdzamy, \
e teza zachodzi dla . Wówczas i jest to rzeczywiście liczba przekątnych
trójkąta.
2. Krok indukcyjny. Przypuśćmy, \
e oraz jest prawdziwe. Udowodnimy .
W tym celu rozwa\
my -kąt wypukły o wierzchołkach . Wówczas są
wierzchołkami -kąta wypukłego , który z zało\
enia indukcyjnego ma przekątnych.
Przekątne to dokładnie przekątne i dodatkowo przekątnych lączących z
wierzchołkami oraz przekątna .
A
ącznie liczba przekątnych wynosi
co kończy dowód.
Definicje rekurencyjne (indukcyjne).
Jeśli dana jest liczba i funkcja o dziedzinie , to mo\
emy zdefiniować nową funkcję o
dziedzinie (czyli: ciąg), która spełnia następujący układ warunków
W definicji tej podajemy wartość funkcji dla argumentu , a następnie wyznaczamy wartości dla
kolejnych liczb naturalnych posługując się rekurencyjnym warunkiem . W
wariantach tej metody mo\
emy określać wartości funkcji dla kilku początkowych argumentów, a
następnie w warunku rekurencyjnym wartość moze zale\
eć od wartości dla kilku poprzednich
argumentów. W ten sposób definiujemy poni\
ej ciąg Fibonacciego. U\
ywając zasady indukcji
matematycznej mo\
na udowodnić, \
e w istocie istnieje jedyna funkcja określona tymi warunkami.
A
atwiej jednak zrozumieć ten fakt na przykładzie.
Przykład. Ciąg Fibonacciego określony jest warunkami
Mamy więc i tak dalej. Ogólnie
mo\
na udowodnić (przez indukcję), \
e
Schemat definicji rekurencyjnej funkcji i więcej zmiennych wygląda podobnie. oznacza tu liczbę
naturalną, zaś i są danymi funkcjami o odpowiednich dziedzinach. Wówczas definiujemy nową
funkcje określoną warunkami
Przykład. Niech oznacza funkcję następnika, tzn. . U\
ywając tej funkcji
mo\
emy zdefiniować rekurencyjnie dwuargumentowe funkcje dodawania i mno\
enia liczb naturalnych.
Podobnie definiujemy potęgowanie, tzn funkcję dwuargumentową dla i .
ściśle rzecz biorąc, operacje i równie\
są zdefiniowane rekurencyjnie (dla danego
ciągu ).
W wielu definicjach i rozumowaniach przeprowadzanych pozornie bez u\
ycia indukcji tkwi ona jednak
ukryta pod sformułowaniami typu ``i tak dalej'' lub napisami typu `` ''. Odnosi się to równie\
często do
sytuacji, gdzie zastępujemy dowód u\
ywający jawnie indukcji matematycznej przez dowód jakoby do tej
zasady się nie odwołujący.