Notatki z wykładu 2 - Indukcja matematyczna PDF

Preview

Summary

Indukcja matematyczna...

Description

MATEMATYKA DYSKRETNA

2021-03-01

Indukcja matematyczna W matematyce wiele twierdzeń dotyczy liczb naturalnych, twierdzenia te opisują pewne równości , nierówności czy podzielność. Przykłady takich właśnie twierdzeń są następujące: 1.Dla każdej dodatniej liczby naturalnej n różnica 10𝑛 −4 jest podzielna przez 6 Twierdzenie to możemy również zapisać następująco:

⋀ 𝑛∈𝑁+ 6|10n − 4

lub tak: ⋀ 𝑛∈𝑁+ ⋁𝑠∈𝑁+ 10𝑛 −4 = 6⋅𝑠

2. Dla każdej dodatniej liczby naturalnej n zachodzi równość: 1+3+5+⋯ +(2𝑛−1) =𝑛2 3. Dla każdej dodatniej liczby naturalnej n zachodzi nierówność: 2𝑛 >𝑛 4. Dla każdej dodatniej liczby naturalnej n zachodzi równość: 12 +22 +32 +⋯ +𝑛2 =

𝑛(𝑛+1)(2𝑛+1) 6

Indukcja matematyczna (nazywana również indukcją zupełną) jest metodą dowodzenia twierdzeń dotyczących liczb naturalnych. Najstarszy dowód indukcyjny podał włoski matematyk Francesco Maurolico w pracy „Dwie księgi o arytmetyce” opublikowanej w 1575 roku. Przedstawiony dowód dotyczył początkowych liczb nieparzystych. Często używaną ilustracją jest efekt domina jeśli ustawimy w szereg kostki domina , jedna za drugą i przewrócimy pierwszą to ona przewraca drugą, druga przewraca trzecią , trzecia czwartą i tak dalej… Indukcja matematyczna jest podstawowym narzędziem służącym do dowodzenia ciągów zdań i jest jednym z podstawowych narzędzi wykorzystywanych w dowodzeniu twierdzeń i definiowaniu pojęć matematyki dyskretnej. Jest konsekwencją zasady dobrego uporządkowania zbioru liczb naturalnych (tzn. że każdy jego podzbiór ma element najmniejszy – zasada minimum). Metoda indukcji matematycznej opiera się na następującej zasadzie: Jeżeli mamy pewne twierdzenie Tn o liczbie naturalnej n , to aby udowodnić, że twierdzenie jest prawdziwe dla każdej liczby naturalnej n nie mniejszej od 𝑛0 (𝑛0 może być zerem, jedynką lub ustaloną inną liczbą naturalną) wystarczy dowieść, że: 1) twierdzenie 𝑇𝑛0 jest prawdziwe; (sprawdzenie warunku początkowego) 2) dla każdej liczby naturalnej 𝑘≥𝑛0 z prawdziwości twierdzenia 𝑇𝑘 wynika prawdziwość twierdzenia 𝑇𝑘+1 , to twierdzenie 𝑇𝑛 jest prawdziwe dla każdej liczby naturalnej 𝑛 ≥𝑛0 (krok indukcyjny: założenie indukcyjne , teza indukcyjna) Dowód przeprowadzony powyższą metodą nazywamy dowodem indukcyjnym. Pierwszy krok dowodu indukcyjnego jest zwykle dość prosty, ale nie można go pominąć. Dowód indukcyjny jest prawidłowo przeprowadzony tylko wtedy, gdy żaden z dwóch kroków nie jest pominięty. Metodę indukcji matematycznej stosujemy w sytuacjach, gdy: - znamy na początku odpowiedź, - wiemy jak wyprowadzić odpowiedź w danym kroku na podstawie odpowiedzi w kroku poprzednim, - gdy zgadujemy ogólne rozwiązanie.

MATEMATYKA DYSKRETNA

2021-03-01

Przykład 1

Udowodnić metodą indukcji matematycznej, że dla każdej liczby naturalnej dodatniej n różnica 𝟏𝟎𝒏 −𝟒 jest podzielna przez 6. Przyjmując 𝑎𝑛 = 10𝑛 −4 mamy udowodnić 𝑇𝑛 , które brzmi: dla każdej liczby naturalnej n liczba 𝑎𝑛 jest podzielna przez 6. Krok 1 Sprawdzamy prawdziwość tezy dla kilku pierwszych wartości n 𝑛=1

𝑎1 = 101 −4 = 6,

𝑛=2

𝑎2 = 102 −4 = 96= 6∙ 16

oczywiście liczba 6 jest podzielna przez 6 więc 𝑇1 jest prawdziwe więc 𝑇2 jest prawdziwe

Krok 2 Niech k będzie dowolną liczbą naturalną dodatnią. Wykażemy, że z podzielności 𝑎𝑘 przez 6 wynika podzielność 𝑎𝑘+1 przez 6. 𝟏𝟎𝒌 −𝟒 = 𝟔∙𝒔

Założenie:

⋀𝑘𝜖𝑁+ ⋁𝑠𝜖𝑁

Teza :

⋀𝑘+1𝜖𝑁+ ⋁𝑡𝜖𝑁 𝟏𝟎𝒌+𝟏−𝟒 = 𝟔∙𝒕

Dowód: 𝑎𝑘+1= 10𝑘+1−4 = 10𝑘 ∙ 10−4 = 10∙ 10𝑘 − 40+ 36= 10 (10𝑘 −4 ⏟) =6 (10𝑠 ⏟ +6) =6𝑡

z założenia

+ 36= 10∙ 6𝑠+6∙ 6 =

𝑡𝜖𝑁+

c.n.d.

Czyli dla każdej liczby naturalnej k z prawdziwości twierdzenia 𝑇𝑘 wynika prawdziwość twierdzenia 𝑇𝑘+1 . Na podstawie zasady indukcji matematycznej stwierdzamy, że dla każdej liczby naturalnej n liczba 𝑎𝑛 = 10𝑛 −4 jest podzielna przez 6.

Przykład 2 Udowodnij, że dla każdej liczby naturalnej dodatniej n zachodzi równość: 𝟏+𝟑+𝟓+⋯ +(𝟐𝒏−𝟏) =𝒏𝟐 Zastosujmy dowód indukcyjny. Krok 1 Sprawdzenie poprawności twierdzenia dla początkowych wartości n 𝑛=1

1 = 12 =1

𝑛=2

1 + 3 = 4 = 22

𝑛=3

1 + 3 + 5 = 9 = 32

Wzór jest prawdziwy dla początkowych liczb naturalnych dodatnich.

MATEMATYKA DYSKRETNA

2021-03-01

Krok 2 Założenie :

⋀𝑘𝜖𝑁+ 1+3+5+⋯ +

Teza:

⋀𝑘+1𝜖𝑁+ 1+3+5+⋯ +

(2𝑘−1) =𝑘 2 (2𝑘 −1) + (2𝑘 +1) = (𝑘+1)2

(Tezę otrzymujemy wstawiając do wzoru z założenia w miejsce k liczbę k+1 1+3+5+⋯ +(2𝑘 −1) + (2(𝑘+1) −1) = (𝑘 +1)2 1+3+5+⋯ +(2𝑘 −1) + (2𝑘+2−1) = (𝑘 +1)2 1+3+5+⋯ +(2𝑘 −1) + (2𝑘+1) = (𝑘 +1)2 ) Dowód: Zapisujemy lewą stronę tezy 𝐿 = 1+3+5+⋯ +(2𝑘−1) ⏟ 𝑧 𝑧𝑎ł𝑜ż𝑒𝑛𝑖𝑎

+ (2𝑘 +1) = 𝑘 2 + (2𝑘+1) =𝑘 2 +2𝑘+1 = (𝑘 +1)2 =𝑃 c.n.d.

Na mocy indukcji matematycznej stwierdzamy prawdziwość dowodzonej równości dla każdej dodatniej liczby naturalnej n.

Przykład 3 Udowodnij, że dla każdej dodatniej liczby naturalnej n zachodzi nierówność: 2𝑛 >𝑛 Stosujemy dowód indukcyjny. Krok 1 Pokazujemy prawdziwość tezy dla początkowych liczb naturalnych dodatnich Dla n=1

21 >1

2>1

Dla n=2

22 > 2

4>2

Krok 2 Wykażemy, że z prawdziwości tezy dla każdej dodatniej liczby naturalnej k wynika prawdziwość dla każdej liczby k+1 Założenie indukcyjne:

⋀ 𝑘𝜖𝑁+ 2𝑘 >𝑘

Teza indukcyjna:

⋀ 𝑘+1𝜖𝑁+ 2𝑘+1> 𝑘+1

Dowód: 2𝑘+1=2𝑘 ∙2 > 𝑘 ∙2 Powyżej wykorzystaliśmy założenie indukcyjne ( zaznaczone na czerwono) i ciąg dalszy 2𝑘+1=2𝑘 ∙2 > 𝑘 ∙2 = 𝑘 +𝑘 ≥ 𝑘 +1 Zatem wykazaliśmy poprawność tezy indukcyjnej 2𝑘+1≥ 𝑘+1 jeśli 2𝑘 >𝑘 c.n.d. Na mocy indukcji matematycznej udowodniliśmy, że

2𝑛 >𝑛 zachodzi dla każdej naturalnej dodatniej liczby n.

MATEMATYKA DYSKRETNA

2021-03-01

Przykład 4 Wykaż, że dla każdej dodatniej liczby naturalnej n 𝟏𝟐 +𝟐𝟐 +𝟑𝟐 +⋯ +𝒏𝟐 =

𝒏(𝒏+𝟏)(𝟐𝒏+𝟏) 𝟔

Krok 1 1(1+1)(2+1)

Sprawdzenie równości dla n=1:

12 =

Sprawdzenie równości dla n =2

12 +22 =

6

=

1∙2∙3 6

=

6 6

=1

2(2+1)(2∙2+1) 6

1+4 =

2∙3∙5

5=5

6

Krok 2 ⋀ 𝑘∈𝑁+ 12 +22 + 32 +⋯ +𝑘 2 =

Założenie indukcyjne:

𝑘(𝑘+1)(2𝑘+1) 6

⋀ 𝑘+1𝜖𝑁+ 12 +22 +32 +⋯ +𝑘 2 + (𝑘 +1)2

Teza indukcyjna:

(𝑘+1)(𝑘+1+1)(2(𝑘+1)+1) 6

=

=

(𝑘+1)(𝑘+2)(2𝑘+3) 6

Dowód: Zapiszmy lewą stronę równości i podstawmy założenie 𝐿=12⏟+22 +32 +⋯ +𝑘2

+ (𝑘 +1)2 =

𝑘(𝑘+1)(2𝑘+1)

𝑧 𝑧𝑎ł𝑜ż𝑒𝑛𝑖𝑎 (𝑘+1)(𝑘(2𝑘+1)+6(𝑘+1)) 𝑘(𝑘+1 )(2𝑘+1)+6(𝑘+1)2 = 6 6

6

=

+ (𝑘 +1)2 =

(𝑘+1)(2𝑘 2 +𝑘+6𝑘+6) 6

=

𝑘(𝑘+1)(2𝑘+1 ) 6

+

(𝑘+1)(2𝑘 2 +7𝑘+6) 6

6(𝑘+1)2 6

=

=

(𝑘+1 )(𝑘+2)(2𝑘+3) 6

=𝑃 c.n.d.

Równość zachodzi dla n=1 , n=2 i dla każdej dodatniej liczby naturalnej z prawdziwości równości dla k wynika prawdziwość dla k+1, więc na podstawie zasady indukcji matematycznej równość ta jest prawdziwa dla każdej dodatniej liczby naturalnej n.

Przykład 5 Wykaż, że dla każdej liczby naturalnej n nie mniejszej od 1 zachodzi równość: 𝑛+1 𝑛 𝑥 2 +𝑥2 +1 𝑛 𝑛−1 (𝑥2 −𝑥 +1)(𝑥 4 −𝑥2 +1)⋅. . .⋅(𝑥 2 −𝑥2 +1) = 𝑥 2 +𝑥 +1 Krok 1 Sprawdzenie równości dla n=1: (𝑥 2 −𝑥 +1) =

𝑥 4 +𝑥2 +1

𝑥 2 +𝑥+1

⇔ (𝑥 2 −𝑥 +1)(𝑥 2 +𝑥+1) =𝑥 4 +𝑥 2 + 1 ⇔ (𝑥2 +1)2 −𝑥 2 =𝑥 4 +𝑥2 +1

Krok 2 Założenie indukcyjne:

⋀𝑘∈𝑁+

𝑘

(𝑥 2 −𝑥 +1)(𝑥4 −𝑥 2 +1)⋅.. .⋅(𝑥 2 −𝑥 2

𝑘−1

+1) =

𝑘+1

𝑥2

Teza indukcyjna: ⋀𝑘+1∈𝑁+

𝑘

(𝑥 2 −𝑥 +1)(𝑥 4 −𝑥 2 +1) ⋅. . .⋅(𝑥 2 −𝑥 2

𝑘−1

+1) (𝑥2

𝑘+1

𝑘

𝑘

+𝑥 2 +1

−𝑥2 +1) =

𝑥 2 +𝑥+1

𝑘+2

𝑥2

𝑘+1

+𝑥 2

+1 𝑥 2 +𝑥+1

MATEMATYKA DYSKRETNA

2021-03-01

Dowód: 𝑘

𝐿=(𝑥 2 −𝑥 +1)(𝑥4 −𝑥 2 +1)⋅. . .⋅(𝑥 2 −𝑥2 =

𝑘−1

+1)(𝑥 2

𝑘+1

𝑘

−𝑥 2 +1) =

𝑘+1 2 𝑘+1 𝑘 𝑘 (𝑥 2 ) +2𝑥 2 +1−𝑥 2 ⋅2 +1)2 −(𝑥2 )2 = 𝑥 2 +𝑥+1 𝑥 2 +𝑥+1

𝑘+1

(𝑥 2

𝑘+1

𝑥2

=

𝑘

+𝑥 2 +1 𝑘+1 ⋅2

𝑥2

𝑥 2 +𝑥+1 𝑘+1

⋅(𝑥 2 𝑘+1

+2𝑥 2 +1−𝑥 2 𝑥 2 +𝑥+1

𝑘+1

𝑘

−𝑥2 +1) =

=

𝑘+2

𝑥2

𝑘+1

+𝑥 2 +1 𝑥 2 +𝑥+1

=𝑃 c.n.d.

Przykład 6 Udowodnijmy , że liczba 21100 - 2120 jest wielokrotnością 10. Zauważmy na początku, że 21 jest liczbą nieparzystą, więc 21100 i 2120 są również liczbami nieparzystymi, ale już ich różnica jest podzielna przez 2. Tak więc wystarczy teraz jeszcze pokazać, że różnica ta jest też podzielna przez 5. Ponieważ 21100=(2120)5, więc być może dla każdej liczby naturalnej n zachodzi własność:

5| n5-n ?

(czytamy: 5 dzieli różnicę n5-n) Krok 1 Sprawdzenie podzielności: dla n=0 mamy 5|05-0=0 dla n=1 mamy 5|15-1=0 dla n=2 mamy 5|25-2=30 Do tej pory własność jest prawdziwa. Krok 2 Założenie indukcyjne: Teza indukcyjna:

⋀ 𝑘∈𝑵

5|𝑘5 −𝑘

⋀𝑘+1∈𝑵 5|(𝑘+1)5 − (𝑘 +1)

Dowód: (𝑘 +1)5 − (𝑘 +1) = 𝑘 5 +5𝑘4 + 10𝑘 4 + 10𝑘 3 +5𝑘 2 +1 −𝑘 −1 = 𝑘5 −𝑘⏟

5| na mocy założenia

+5(𝑘 4 +2𝑘4 +2𝑘 3 + 𝑘 2 )

Pokazaliśmy, że 5 dzieli n5-n dla każdego n a więc także dla n=2120 . Ostatecznie wykazaliśmy podzielność przez 2 i przez 5 a więc i przez 10.

Źródła Źródła: M. Kurczab, E. Kurczab, E. Świda, Matematyka, Oficyna Wydawnicza Krzysztof Pazdro, Warszawa 2016 K. A. Ross, C. R. B. Wright, Matematyka dyskretna, PWN, Warszawa 2008 W. Leksiński , B. Macukow, W. Żakowski , Matematyka w zadaniach dla Kandytów na wyższe uczelnie techniczne, WNT H. Pawłowski , Matematyka , Operon 2003 Wykłady dr inż. J. Pozorskiej (niepublikowane) Opracowania własne

c.n.d....