5600235753

4 Indukcja matematyczna 10

n			2 ^n
0	o II o	<	2° = 1
1	1 = 1^2	<	2^1 = 2
2	4 = 2^2	<	2^2 = 4
3	9 = 3^2	<	2^3 = 8
4	16 = 4^2	■L	2^4 = 16
5	ND II cn	<	<M n II
6	36 = 6^2	<	2^6 = 64

Udowodnimy, że wzór (3) jest prawdziwy dla wszystkich n > 6. Zakładamy, że dla k wzór ten zachodzi. Sprawdzimy, czy zachodzi również dla A; + 1. Korzystając z znaszego założenia i z przykładu 4.4 mamy

(k + l)² = fc² + 2k + 1 < 2^k + 2^k = 2 • 2^k = 2*⁺¹,

co oznacza, że wzór (3) jest prawdziwy dla A; + 1.

4.3    Zasada indukcji zupełnej

Twierdzenie 4.6. Niech S C N, n € N spełniają warunek:

(i) jeśli (n, n + 1, n + 2,..., A;} C S, to k + 1 G S.

Wówszas {n,n + l,n + 2,..,}CS,

Przykład 4.7. Mamy prostokątną czekoladę złożoną z n = ab, gdzie 0 < a, 6, kwadratowych kawałków. Przez ułamanie rozumiemy rozcięcie wzdłóż linii pomiędzy kawałkami, tak aby dostać dwa prostokątne kawałki. Ile razy trzeba ułamać czekoladę aby rozdzielić jej wszystkie kawałki?

Stosując zasadę indukcji zupełnej pokażemy, że trzeba wykonać n — 1 ułamań. Najmniejsze możliwe aib to a = b= 1. Zatem najmniejsza czekolada składa się z n = ab = 1 kawałków i do jej podzielenia wystarczy n — 1 = 0 ułamań.

Zgodnie z zasadą indukcji zupełnej rozważmy zbiór

S := {n G N: dla prostokątnej czekolady o n kawałkach potrzeba n — 1 ułamań}

i załóżmy, że {0,1,2,..., A;} C S. Pokażemy, że A; + 1 € S. Gdy czekolada ma A; + 1 kawałków, to pierwsze ułamanie podzieli ją na dwa prostokąty złożone z odpowiednio k\ i k% kawałków, przy czym Aą-f A^ = A; + l oraz 1 < k\,k2- Zauważmy, że ki,k2 £ S, to znaczy, że aby połamać te mniejsze kawałki potrzeba odpowiednio k\ — 1 oraz A^2 — 1 ułamań. W sumie, od początku, wykonaliśmy więc

1 + ki - 1 + k₂ - 1 = (A: + 1) - 1

ułamań, co kończy dowód.

4.4    Zasada maksimum

Twierdzenie 4.8. W każdym niepustym i ograniczonym z góry podzbiorze zbioru liczb naturalnych jest element największy.