Indukcja Matematyczna ( 1)

Matematyka D ys kr etna

I

I

N

N

D

D

U

U

K

K

C

C

J

J

A

A

M

M

A

A

T

T

E

E

M

M

A

A

T

T

Y

Y

C

C

Z

Z

N

N

A

A

K i l k a p r z y k ł a d ó w :

( 1 ) K i e d y ś w i e d z i a ł e m c o t o i n d u k c j a . K a ż d e g o d n i a j e ś l i d z i e ń

w c z e ś n i e j w i e m c z y m j e s t i n d u k c j a , t o i t e g o d n i a t e ż w i e m ( b o n i e

z a p o m i n a m n i c z e g o z d n i a n a d z i e ń ) .

( 2 ) Z a p i s a ł e m d z i s i e j s z y w y k ł a d w 1 2 5 0 l i n i j k a c h . J e ś l i p o t r a f i ę c o ś

z a p i s a ć w n l i n i k a c h t o p o t r a f i ę t o t e ż z a p i s a ć w n – 1 l i n i j k a c h ( o i l e

n

> 1 ) .

( 3 )

)

(

)

(

q

r

p

r

q

p

•

↔

•

↔

)

(

)

(

r

q

r

p

q

p

•

↔

•

↔

g d z i e • ∈ { ∨, ∧, →, ↔, ⊕}

)

(~

)

(~

q

p

q

p

↔

↔

| = p → ( q → ( ( ~ p ∨ ~ q) → r))

| = ( ~ p ∨ ~ q) ↔ ( ~ q ∨ ~ p)

? p → ( q → ( ( ~ q ∨ ~ p) → r))

Indukcja Matematyczna ( 2)

Matematyka D ys kr etna

(4) Regulamin.

§ 1

N a w y k ł ad z ie o b ec no ś ć j es t o b o w ią z k o w a j ed y nie d la t y c h s t ud ent ó w ,

k t ó r z y nie o p uś c ili d o t ej p o r y ż ad nego w y k ł ad u o r az d la t y c h , k t ó r z y

d o p uś c ili s ię w y k r o c z enia p r z ec iw t emu r egulamino w i.

(5 ) I le b y o s ó b nie b y ł o j uż w t y m aud y t o r ium, t o i t ak z aw s z e s ię

j es z c z e j ed na z mieś c i.

Indukcja Matematyczna ( 3)

Matematyka D ys kr etna

Aksjomat indukcji wyjęty wprost z teorii arytmetyki:

(tak naprawdę jest to sch emat g enerują cy nieskoń czenie wiel e aksjo-

mató w)
D l a każ deg o predykatu P:

|- [ P(1 ) ∧ ∀

k

(P(k) → P(k + 1 ) ) ] → ∀

k

(P(k) )

T wierdzenie:

∀

k

(1 + 2 + . . . + k = k(k + 1 ) / 2 )

K rok 1 : D ef iniujemy P(k) ⇔ 1 + 2 + . . . + k = k(k + 1 ) / 2

K rok 2 : D owodzimy P(1 ) : 1 = 1 ⇒ P(1 )

K rok 3 : D owodzimy P(k) ⇒ P(k + 1 ) (dl a k ∈ N):

P(k) ⇔

1 + 2 + ... + k = k(k + 1 ) / 2 ⇔

1 + 2 + ... + k + (k + 1 ) = k(k + 1 ) / 2 + (k + 1 ) ⇔

1 + 2 + ... + k + (k + 1 ) = (k + 1 ) (k + 2 ) / 2 ⇔

P(k + 1 )

*

Z a s a d a i n d u k c j i n r 1
D l a d o w o l n e j f u n k c j i z d a n i o w e j P(k), a b y u d o w o d n i ć ∀

k

(P(k))

w y s t a r c z y p o k a z a ć , ż e P(1 ) o r a z ż e P(k) ⇒ P(k + 1 ) p r z y j m u j ą c , ż e

u n i w e r s u m j e s t N.

J a k u d o w o d n i c t w i e r d z e n i e :

J e ż e l i k ∈ N, k ≥ 4 t o 2

k

≥ k

2

C h c i a ł o b y s i ę p r z y j ą ć P(k) ⇔ 2

k

≥ k

2

a l e ... w ó w c z a s m a m y ~ P(3 ).

Indukcja Matematy cz na ( 4)

Matematy ka D y s kr etna

Zasada indukcji nr 2 (w troszkę ogólniejszej wersji):
D la dowolnej f unkcji zdaniowej P(k), ab y udowodnić ∀

k ≥ s

(P(k) )

w y s t a r c z y p o k a z a ć , ż e P(s) o r a z ż e

k ≥ s ∧ P(k) ⇒ P(k + 1 )

p r z y j m u j ą c , ż e u n i w e r s u m j e s t N.

D o w ó d : (k o r z y s t a m y z z a s d y i n d u k c j i n r 1 )

P r z y p u ś ć m y , ż e :

(1 ) P(s) o r a z

(2 ) k ≥ s ∧ P(k) ⇒ P(k + 1 ) .

M a m y p o k a z a ć : ∀

k ≥ s

(P(k) )

K r o k 1 : N i e c h Q(k) ⇔ P(k) ∨ k < s.

K r o k 2 : D o w o d z i m y Q(1 ) :

G d y s = 1 t o m a m y Q(1 ) z (1 ) i z d e f . Q

G d y s > 1 t o m a m y Q(1 ) b e z p . z d e f . Q

K r o k 3 : D o w o d z i m y Q(k) ⇒ Q(k + 1 )

R o z p a t r z m y n a s t ę p u j ą c e m o ż l i w e w a r t o ś c i k:

(1 ) k + 1 < s: W ó w c z a s p o p r z e d n i k i n a s t ę p n i k Q(k) → Q(k + 1 ) s ą

p r a w d z i w e b e z p . z d e f . Q.

(2 ) k + 1 = s: W ó w c z a s z (1 ) n a s t ę p n i k i m p l i k a c j i Q(k) → Q(k + 1 )

j e s t p r a w d z i w y .

(3 ) k + 1 > s: W ó w c z a s z d e f . Q m a m y Q(k) ↔ P(k) o r a z Q(k + 1 ) ↔

P(k + 1 ) , a z (2 ) m a m y P(k) → P(k + 1 ) c o w e f e k c i e d a j e Q(k) → Q(k

+ 1 )

Z (1 ) , (2 ) , (3 ) o t r z y m u j e m y Q(k) ⇒ Q(k + 1 )

S t ą d , n a p o d s t a w i e p o p r z e d n i e j z a s a d y i n d u k c j i m a m y :

∀

k

(Q(k) ) ⇔

∀

k

(P(k) ∨ k < s) ⇔

∀

k

(k ≥ s → P(k) ) ⇔

∀

k ≥ s

(P(k) )

*

Indukcja Matematyczna ( 5)

Matematyka D ys kr etna

Wróćmy do naszego twierdzenia:

dowód: (z zasady indu k c j i nr 2 )

K rok 1 : D ef iniu j emy P(k) ⇔ 2

k

≥ k

2

K rok 2 : D owodzimy P(4 ) : 2

4

= 4

2

⇒ P(4 )

K rok 3 : D owodzimy P(k) ⇒ P(k + 1 ) (dl a k ∈ N, k ≥ 4 ) :

P(k) ∧ k ≥ 4 ⇔

2

k

≥ k

2

∧ k ≥ 4 ⇒

(2

k+ 1

≥ k

2

+ k

2

> k

2

+ 2k + 1 = (k + 1 )

2

) ∧ k ≥ 4 ⇒ / / k > 1 +

2

⇒

P(k + 1 ) / / k

2

> 2k + 1

A r c h i p e l a g n w y s p j e s t o b s ł u g i w a n y p r z e z t o w a r z y s t w o l o t n i c z e w

taki sposób, że dla dowolnych dwóch wysp istnieje bezpośrednie

poł ą czenie lotnicze ale tylko w jedną stronę . ( S am olot lata z wyspy A

na wyspę B ale nie lata z B na A) . J ak u dowodnić , że m ożna zwiedzić

ten archipelag odwiedzają c wszystkie wyspy w taki sposób, żeby na

każdej być tylko raz?

D owód indu kcyjny ze wzg lę du na liczbę wysp.

K rok począ tkowy: D la n = 1 , 2 prawdziwość tezy jest oczywista.

K rok indu kcyjny: P rzypu ść m y, że twierdzenie jest prawdziwe dla

wszystkich k < n.

W ybierzm y dowolną wyspę A.

Niech I oznacza zbiór tych wysp, z których lata sam olot do A.

Niech O oznacza zbiór tych wysp, do których lata sam olot z A.

O czywiście | I| < n oraz | O| < n.

Z zał . indu kcyjneg o zarówno I jak i O m ożna zwiedzić odwiedzają c

każdą wyspę teg o zbioru dokł adnie raz.

O statecznie cał y archipelag m ożna zwiedzić zwiedzają c zg odnie z

powyższą m etodą podarchipelag I nastę pnie wyspę A i wreszcie

podarchipelag O.

*

Indukcja Matematyczna ( 6)

Matematyka D ys kr etna

Zasada indukcji nr 3 (w jeszcze ogólniejszej wersji):
D la dowolnej f unkcji zdaniowej P(k), ab y udowodnić ∀

k ≥ s

(P(k) )

w y s t a r c z y p o k a z a ć , ż e P(s) o r a z ż e

k ≥ s ∧ ∀

k ≥ r ≥ s

(P(r) ) ⇒ P(k + 1 )

p r z y j m u j ą c , ż e u n i w e r s u m j e s t N.

D o w ó d : (k o r z y s t a m y z z a s d y i n d u k c j i n r 2 )

P r z y p u ś ć m y , ż e :

(1 ) P(s) o r a z

(2 ) k ≥ s ∧ ∀

k ≥ r ≥ s

(P(r) ) ⇒ P(k + 1 )

M a m y p o k a z a ć : ∀

k ≥ s

(P(k) )

K r o k 1 : N i e c h Q(k) ⇔ ∀

k ≥ r ≥ s

(P(r) ) .

K r o k 2 : D o w o d z i m y Q(s) : Q(s) j e s t s p e ł n i n e b e z p o ś r e d n i o z d e f . Q

o r a z z (1 ) .

K r o k 3 : D o w o d z i m y k ≥ s ∧ Q(k) ⇒ Q(k + 1 ) :

k ≥ s ∧ Q(k) ⇔ // z def. w kroku 1

k ≥ s ∧ ∀

k ≥ r ≥ s

(P(r) ) ⇒ // z (2 )

∀

k ≥ r ≥ s

(P(r) ) ∧ P(k + 1) ⇔ ∀

k+ 1 ≥ r ≥ s

(P(r) ) ⇔ Q(k + 1)

Z g odn i e z za s a dą i n dukc j i n r 2 udowodn i l i ś m y : ∀

k ≥ s

(Q(k) ) .

∀

k ≥ s

(Q(k) ) ⇔ ∀

k ≥ s

(∀

k ≥ r ≥ s

(P(r) ) ) ⇒ ∀

k ≥ s

(P(k) )

*

Czy można używać indukcji do dowodzenia własności innych

ob iekt ó w niż zb ió r l iczb nat ur al nych (z ewent ual nym p ominię ciem

p ewneg o p r zedziału { 1 , 2 , . . . , k} ) ?

D l a p ewneg o zb ior u A chcemy udowodnić, że ∀

x∈A

(P(x) ) . M ożemy

wykor zyst ać mechanizm indukcji, jeżel i p ot r af imy znal eź ć sur jekcję

f : N → A or az p okazać p r zez indukcję , że ∀

n∈N

(Q(n) ) p r z y j m u j ą c

Q(n) ⇔ P(f(n) ) .

Indukcja Matematyczna ( 7)

Matematyka D ys kr etna

P r z y k ł a d : ( NP - z b i ó r l i c z b n i e p a r z y s t y c h )

T w i e r d z e n i e ∀

k∈NP

(1 + 3 + 5 + ... + k = (k + 1)

2

/ 4 ) .

D o w ó d :

N i e c h P(x) ⇔ 1 + 3 + 5 + ... + x = (x + 1)

2

/ 4 (d l a x ∈ N P) .

N i e c h f(n) = 2 n – 1.

f j e s t n i e t y l k o s u r j e k c j ą a l e t a k ż e f u n k c j ą w z a j e m n i e j e d n o z n a c z n ą

g d y ż i s t n i e j e f u n k c j a o d w r o t n a f

-1

(x) = (x + 1) / 2 .

K r o k 1: Q(n) ⇔ P(f(n) )

K r o k 2 : 1 = (1 + 1)

2

/ 4

K r o k 3: Q(n) ⇔ 1 + 3 + 5 + ... + 2 n – 1 = (2 n – 1 + 1)

2

/ 4 ⇔

1 + 3 + 5 + ... + 2 (n + 1) – 1 = (2 n – 1 + 1)

2

/ 4 + 2 n + 1 =

(4 n

2

+ 8 n + 4 ) / 4 = (2 n + 2 )

2

/ 4 = (2 (n + 1) – 1 + 1)

2

/ 4 ⇔

Q(n + 1)

C z y m o ż n a s t o s o w a ć i n d u k c j ę d l a p r e d y k a t ó w w i ę c e j n i ż j e d n o -

a r g u m e n t o w y c h ?

P r z y j m u j e m y X = N.

C h c e m y u d o w o d n i ć ∀

k

(∀

r

(P(k, r) ) ) .

K r o k 1: Q(k) ⇔ ∀

r

(P(k, r) )

K r o k 2 : Q(1)

K r o k 3: Q(k) ⇒ Q(k + 1)

Krok 2 oznacza konieczność dowodu ∀

r∈N

(P(1 , r)) w t y m cel u t eż

m oż em y zas t os ować indukcj ę (al e nie m us im y ):

Krok 2. 1 : S(r) ⇔ P(1 , r)

Krok 2. 2: S(1 ) / / m us im y wy kazać p rawdziwość P(1 , 1 )

Krok 2. 3 : S(r) ⇒ S(r + 1 ) / / P(1 , r) ⇒ P(1 , r + 1 )

Indukcja Matematyczna ( 8)

Matematyka D ys kr etna

Zas ad a i n d u k c j i n r 4 (w w e r s j i d l a d w ó c h z m i e n n y c h ) :
D l a d o w o l n e j f u n k c j i z d an i o w e j P(k, r) , ab y u d o w o d n i ć :

∀

k

(∀

r

(P(k, r ) ) )

w y s t ar c z y p o k az ać , ż e P(1 , 1 ) o r az ż e

P(k, r) ⇒ [ P(k + 1 , r) ∧ P(k, r + 1 ) ]

p r z y j m u j ą c , ż e u n i w e r s u m j e s t N.

D o w ó d :

Zał ó ż m y :

(1 ) P(1 , 1 )

(2 ) P(k, r) ⇒ [ P(k + 1 , r) ∧ P(k, r + 1 ) ]

M am y u d o w o d n i ć : ∀

k

(∀

r

(P(k, r ) ) )

Dowód indukcyjny ze względu na k:

K r ok 1 : Q(k) ⇔ ∀

r

(P(k, r ))

K r ok 2 : Q(1 ):

Dowód indukcyjny ze względu na r:

K r ok 2 .1 : T(r) ⇔ P(1 , r)

K r ok 2 .2 : T(1 ): wynika b ezp . z (1 )

K r ok 2 .3 : T(r) ⇒ T(r + 1 ): wynika p r awie b ezp . z (2 )

K r ok 3 : Q(k) ⇒ Q(k + 1 ):

Z (2 ) m am y: P(k, r) ⇒ P(k + 1 , r) czyli

| = P(k, r) → P(k + 1 , r) / / s t os ujem y p r awo uogólniania

| = ∀

r

[P(k, r) → P(k + 1 , r)] / / s t os yjem y odp owiednie p r awo r ach . kw.

| = ∀

r

[P(k, r)] → ∀

r

[P(k + 1 , r)] czyli

∀

r

[P(k, r)] ⇒ ∀

r

[P(k + 1 , r)] co koń czy dodód K r oku 3 .

U dowodniliś m y zat em ∀

k

(Q(k))

*

P r zykł ad:

U dowodnić , ż e 3 | k

3

+ n

3

+ 2 k – n dla k, n ∈ N.

K r ok 1 : P(k, n) ⇔ 3 | k

3

+ n

3

+ 2 k – n

K r ok 2 : P(1 , 1 ): 3 | 1

3

+ 1

3

+ 2 · 1 – 1 ⇒ P(1 , 1 )

Indukcja Matematyczna ( 9)

Matematyka D ys kr etna

Krok 3a: P(k, n) ⇒ P(k + 1 , n):

P(k, n) ⇔

3 | k

3

+ n

3

+ 2 k – n ⇔

3 | k

3

+ n

3

+ 2 k – n + 3k

2

+ 3k + 3 ⇔

3 | k

3

+ 3k

2

+ 3k + 1 + n

3

+ 2 k + 2 – n ⇔

3 | (k + 1 )

3

+ n

3

+ 2 (k + 1 ) – n ⇔

P(k + 1 , n)

Krok 3b : P(k, n) ⇒ P(k, n + 1 ):

P(k, n) ⇔

3 | k

3

+ n

3

+ 2 k – n ⇔

3 | k

3

+ n

3

+ 2 k – n + 3n

2

+ 3n ⇔

3 | k

3

+ n

3

+ 3n

2

+ 3n + 1 + 2 k + 2 – n – 1 ⇔

3 | k

3

+ (n + 1 )

3

+ 2 (k + 1 ) – (n + 1 ) ⇔

P(k, n + 1 )

Indukcja Matematyczna ( 1 0 )

Matematyka D ys kr etna

Ro z w a ż m y j e s z c z e r a z z a s a d ę n r 3 :
D l a d o w o l n e j f u n k c j i z d a n i o w e j P(k) , a b y u d o w o d n i ć ∀

k ≥ s

(P(k) )

w y s t a r c z y p o k a z a ć , ż e P(s) o r a z ż e

k ≥ s ∧ ∀

k ≥ r ≥ s

(P(r) ) ⇒ P(k + 1 )

p r z y j m u j ą c , ż e u n i w e r s u m j e s t N.

Z p r a w a k o n r a p o z y c j i i m p l i k a c j ę i n d u k c y j n ą m o ż e m y z a s t ą p i ć

f o r m u ł ą : ~ P(k + 1 ) ⇒ k < s ∨ ∃

k ≥ r ≥ s

(~P(r) ) , a d a l e j w o p a r c i u o

o d p o w i e d n i ą t a u t o l o g i ę r a c h . z d . (j a k ą ? ) :

~P(k + 1 ) ∧ k ≥ s ⇒ ∃

k ≥ r ≥ s

(~P(r) )

d l a s = 1 m a m y p r o s t s z ą p o s t a ć : ~P(k + 1 ) ⇒ ∃

r ≤ k

(~P(r))

P o w y ż s z a f o r m u ł a p o z w a l a n a p r z e p r o w a d z a n i e d o w o d ó w i n d u k c y j -

n y c h w n a s t ę p u j ą c e j f o r m i e :

K r o k 1 : D o w o d z i m y P(1 )

K r o k 2 : P r z y p u ś ć m y , ż e k j e s t n a j m n i e j s z ą l i c z b ą n a t u r a l n ą d l a k t ó r e j

~P(k). P o k a z u j e m y , ż e i s t n i e j e r < k d l a k t ó r e g o ~P(r).

Z a s a d a i n d u k c j i n r 5 :
D l a d o w o l n e j f u n k c j i z d a n i o w e j P(k), a b y u d o w o d n i ć ∀

k ≥ s

(P(k) )

w y s t a r c z y p o k a z a ć , ż e P(s) o r a z ż e

~P(k + 1 ) ∧ k ≥ s ⇒ ∃

k ≥ r ≥ s

(~P(r) )

p r z y j m u j ą c , ż e u n i w e r s u m j e s t N

.

Indukcja Matematyczna ( 1 1 )

Matematyka D ys kr etna

Przypuśćmy, że dla pewnej funkcji zdaniowej P(n) pot rafimy pokazać

dla pewnej liczb y c ∈ N:

(1 ) P(1 )

(2 ) P(n) ⇒ P(cn)

(3 ) P(n) ∧ n > 1 ⇒ P(n – 1 )

C zy na t ej pods t awie możemy udowodnić ∀

n

(P(n)) ?

Z zas dy indukcji (1 ) i (2 ) dają nat ych mias t ∀

k

(P(c

k

))

Dowolną liczbę n ∈ N m oż na p r ze d s t a wić w p os t a ci c

k

– r d obie r a j ąc

p e wne liczby na t u r a lne k i r.

P r zy j m u j ąc







≥

<

−

⇔

k

k

k

k

c

r

c

r

r

c

P

r

Q

dla

dla

)

(

)

(

1

gdzie r ∈ N ∪ { 0 }

m a m y P(c

k

) ⇔ Q

k

(0 )

A z (3 ) o t r z y m u j e m y Q

k

(r) ⇒ Q

k

(r + 1 )

A z a t e m n a z a s a d z i e i n d u k c j i m a m y ∀

r≥0

(Q

k

(r))

c o z d e f . Q

k

d a j e ∀

r ≤ ck

(P(c

k

– r))

W y b i e r a j ą c d o w o l n e n u d o w o d n i l i ś m y P(n), a z a t e m ∀

n

(P(n)).

Indukcja Matematyczna ( 1 2 )

Matematyka D ys kr etna

Przykład dowodu z i n dukc j ą ws t e c zn ą :

U dowodn i m y, ż e :

n

x

x

x

x

n

n

n

+

+

≤

⋅⋅

⋅

...

1

1

dla dowolnych x

1

, ..., x

n

∈ R

+

i n ∈ N.

N i e ch P(n) ⇔ ∀

x1, . . . , xn









+

+

≤

⋅⋅

⋅

n

x

x

x

x

n

n

n

...

1

1

K r o k 1 a : P(1 ) - o c z y w i s t e

K r o k 1 b : P(2 ) - p r o s t e p r z e k s z t a ł c e n i e a l g e b r a i c z n e

K r o k 2 : P(n) ⇒ P(2 n) :

N i e c h x

1

,..., x

n

, y

1

,...,y

n

b ę d ą d o w o l n y m i l i c z b a m i z R

+

P r z y j m i j m y c

i

= (x

i

y

i

)

1/ 2

P(n) ⇒

n

c

c

c

c

n

n

n

+

+

≤

⋅⋅

⋅

...

1

1

P( 2 ) ⇒

2

i

i

i

y

x

c

+

≤

S t ą d m a m y :

n

y

x

c

c

n

i

i

i

n

n

∑

≤

≤

+

≤

⋅⋅

⋅

1

1

2

/

)

(

⇔

n

y

x

y

x

n

n

n

2

)

...

1

2

1

+

+

≤

⋅⋅

⋅

P o n i e w a ż x

1

,. . . , x

n

, y

1

,. . . ,y

n

b y ł y w y b r a n e d o w o l n i e w i ę c u d o w o d n i l i ś -

m y P(n) ⇒ P(2 n) .

K r o k 3 : P(n) ∧ n > 1 ⇒ P(n – 1 ) :
W y b i e r a m y x

1

,. . . , x

n–1

d o w o l n i e i p r z y j m u j e m y

1

...

1

1

−

+

+

=

−

n

x

x

x

n

n

. Po

z a s t os ow a n i u n i e r ó w n oś c i P(n) i p r os t y c h p r z e k s z t a ł c e n i a c h

a l g e b r a i c z n y c h ot r z y m u j e m y P(n – 1 ) d l a x

1

,..., x

n–1

.

Po n i e w a ż x

1

,..., x

n–1

b y ł y w y b r a n e d o w o l n i e , w i ę c u d o w o d n i l i s m y , ż e

P(n) ∧ n > 1 ⇒ P(n – 1 ) .

Indukcja Matematyczna ( 1 3 )

Matematyka D ys kr etna

N i e c h f

1

, f

2

, . . . b ę d z i e c i ą g i e m d o w o l n y c h f u n k c j i t a k i c h , ż e f

i

: A

i–1

→

A.

I s t n i e j e d o k ł a d n i e j e d e n c i ą g x

1

, x

2

, . . . t a k i , ż e x

i+ 1

= f

i+ 1

(x

1

, x

2

, . . . , x

i

)

D o w ó d - n a t y c h m i a s t z z a s a d y i n d u k c j i .

T a k i s p o s ó b d e f i n i o w a n i a c i ą g u n a z y w a ć b ę d z i e m y

d

d

e

e

f

f

i

i

n

n

i

i

c

c

j

j

ą

ą

r

r

e

e

k

k

u

u

-

-

r

r

e

e

n

n

c

c

y

y

j

j

n

n

ą

ą

.

.

P r z y k ł a d y :

x

1

= a, x

i+ 1

= bx

i

, d l a a, b ∈ R.

x

1

= a, x

i+ 1

= b + x

i

, d l a a, b ∈ R.

x

1

= x

2

= 1 , x

i+ 2

= x

i+ 1

+ x

i

Z i n d u k c j ą t r z e b a p o s t ę p o w a ć o s t r o ż n i e :

W s z y s t k i e k o n i e s ą t e g o s a m e g o k o l o r u b o :

D l a j e d n e g o k o n i a t w i e r d z e n i e z a c h o d z i . Z a ł ó ż m y , ż e t w i e r d z e n i e

z a c h o d z i d l a k a ż d y c h n k o n i i r o z p a t r z m y d o w o l n y z b i ó r n + 1 k o n i A.

N i e c h M i s i o i P t y s i o b ę d ą d o w o l n y m i k o ń m i z A. P o w i e d z m y , ż e

R y s i o j e s t n + 1 k o n i e m . W y r z u ć m y n a c h w i l ę P t y s i a u z y s k u j ą c z b i ó r

n k o n i . A z a t e m M i s i o i R y s i o s ą t e g o s a m e g o k o l o r u . T e r a z z a s t ą p m y

M i s i a P t y s i e m . Z n ó w m a m y n k o n i w i ę c R y s i o i P t y s i o s ą t e g o s a m e g o

k o l o r u . R y s i o j e s t w i ę c t e g o s a m e g o k o l o r u c o P t y s i o i M i s i o , a l e

P t y s i o i M i s i o b y l i w y b r a n i d o w o l n i e , w i ę c R y s i o j e s t t e g o s a m e g o

k o l o r u c o w s z y s t k i e i n n e k o n i e w A.

Indukcja Matematyczna ( 1 4 )

Matematyka D ys kr etna

I

I

n

n

d

d

u

u

k

k

c

c

j

j

a

a

a

a

p

p

r

r

o

o

g

g

r

r

a

a

m

m

o

o

w

w

a

a

n

n

i

i

e

e

J a k d o w o d z i ć p o p r a w n o ś c i p r o g r a m ó w ?

P r z e w a ż n i e c h c e m y m i e ć p e w n o ś ć , ż e b e z p o ś r e d n i o p o l u b p r z e d

w y k o n a n i e m z a d a n e j i n s t r u k c j i w a r t o ś c i z a m i e n n y c h p r o g r a m u b ę d ą

p r z y j m o w a ł y w a r t o ś c i s p e ł n i a j ą c e z a d a n e w a r u n k i .

G d y b y n i e p ę t l e i r e k u r e n c j a p r o g r a m p o s i a d a ł b y s k o ń c z o n ą l i c z b ę

s c i e ż e k o b l i c z e ń , k t ó r e m o ż n a b y b y ł o p r z e a n a l i z o w a ć j e d n a p o

d r u g i e j . J a k z a t e m d o w o d z i ć p o p r a w n o ś c i i n s t r u k c j i p ę t l i ?

O g r a n i c z m y s i ę d o p ę t l i P(w, I) : w h i l e w d o I,

g d z i e w j e s t p e w n y m z d a n i e m , a I c i ą g i e m i n s t r u k c j i p r o g r a m u .

Z d a n i e z n a z w i e m y n i e z m i e n n i k i e m p ę t l i P w t e d y i t y l k o w t e d y g d y

p r a w d z i w o ś ć z d a n i a z ∧ w p r z e d w y k o n a n i e m c i ą g u i n s t r u k c j i I p ę t l i

i m p l i k u j e p r a w d z i w o ś ć z b e z p o ś r e d n i o p o w y k o n a n i u I.

P r z y k ł a d

x = 1 ;

i = 1 ;

w h i l e (i ≤ n) {

x = yx;

i + = 1 ;

}

N i e z m i e n n i k : z ⇔ x = y

i–1

W i e m y w i ę c , ż e j e ż e l i x = y

i–1

w m o m e n c i e r o z p o c z ę c i a p ę t l i w h il e t o

t a k ż e x = y

i–1

p o j e j z a k o ń c z e n i u . W y s t a r c z y z a t e m u s t a l i ć j a k ą

w a r t o ś ć b ę d z i e p r z y j m o w a ć z m i e n n a i.

O i l e t y l k o n ≥ 0 , t o p o w y ż s z y p r o g r a m r e a l i z u j e i n s t r u k c j e :

{ i = n + 1 ; x = y

n

}