2766503935

Dowód indukcyjny (przeprowadzony w oparciu o zasadę indukcji matematycznej). Poprawne rozumowanie indukcyjne wymaga wykonania kroku indukcyjnego (np. że dla n = no wszystko jest prawdą) i co najmniej jednego szczególnego przypadku prawdziwości dowodzonego twierdzenia.

Praktycznie:

(1)    Dowiedź, ze twierdzenie T(n) jest prawdziwe dla no (dla wyrazu pierwszego/początkowego)

(2) Załóż.    że T (k) jest prawdziwe    - przepisujemy wzór dla n = k

Postaw tezę, że T(k + 1) jest prawdziwe

Dowiedź. że Tik) ^ T(fe + 1)    -pokazujemy, że jeżeli twierdzenie (wzór) jest

prawdziwe dla n - k, to jest również prawdziwe dla n = k + 1.

Przykład nr 1_

Udowodnić, że dla każdej liczby naturalnej n > 3 spełniona jest nierówność: 2^,Ł > 2n.

Twierdzenie (hipoteza):    T(n): ( 2ⁿ > 2n ) dla każdej liczby naturalnej n > 3

(1) Twierdzenie:    sprawdzenie prawdziwości T(no): dla no = 3.

T(3):    < 2³ > 2 • 3 ) <J=> (8 > 6 ) <5=5> (L>P) etui.

(2) Założeni e:    zakładamy, że tw. jest prawdziwe dla pewnej liczby naturalnej k.

T(fe):    (2* > 2k)    oraz prawdziwy jest wzór pomocniczy 2* > k

Teza:    twierdzenie dla n = k + 1.

T(A+1):    (2*⁺¹> 2-(fef 1)) <# (2^k+1 > 2fe + 2 )

D o w ó d (krok indukcyjny): pokazujemy prawdziwość implikacji T(h) T(h+1) dla h ^ no.

2^k>2k /-2 o 2^k+1 > 4h o 2*⁺¹ > 2k+2k>2k+2 = 2-(fe + l) <=> 2*⁺¹>2«(fe + l) więc dla każdego /i > 3 mamy Tin) = ( 2ⁿ > 2n) => T(n + 1) = ( 2'¹⁺¹ > 2-(?i + 1) ) ciul.

Przykład nr 2_

n • (n + 1)

Udowodnić, że dla każdej n spełniona jest równość:    1 + 2 + 3 H-----\-n

Twierdzenie (hipoteza):    t(n):    l + 2 + 3 + --- + n = ⁿ Sⁿ + ^

(1) Twierdzenie: sprawdzenie prawdziwości T(no) dla no = 1.

1 • (1 + 1)

T(n= 1):    I L =n=1 A P =

= 1] ° ( L=P)

k • (Tc + 1)

(2) Założenie:    T(n — k): 1+2 + 3 + ••• + & —

Teza:

T(n= A+ 1):    1 + 2 + 3 + -- + /C + (/c + 1) =

yAr + 1) * (Ar + 2)

Dowód:    1+2 + 3 +■■■ + fc + (fc + l)=^fe ^ + (fe + 1) =    ^ ⁺ ^ S^{k + 2}'¹

___„    2    2    cna

założenie str. L

wyraz    założenie wyraz

następny    _sfr p    następny

teza, str. P

teza. str. L

k(k +1)    ,    „ _x (k + 1) ■ 0 + 2)

tak więc: T(k) = 1 + 2 + - + k = ——- => T(k + 1) = 1 + 2 + - + (k + 1) =---

© Copyright by Ewa Kędzi orczyk

-28-

w w w. ma tein atyka. sosno wiec.p /