Zgryźliwość kojarzy mi się z radością, która źle skończyła.
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 .
Łą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.
Łatwiej jednak zrozumieć ten fakt na przykładzie.
Przykład.
Ciąg Fibonacciego określony jest warunkami
zanotowane.pl doc.pisz.pl pdf.pisz.pl hannaeva.xlx.pl
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 .
Łą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.
Łatwiej jednak zrozumieć ten fakt na przykładzie.
Przykład.
Ciąg Fibonacciego określony jest warunkami