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
}