Matematyka dyskretna
Dr Marek Zakrzewski
Wykład 02
REKURSJA I INDUKCJA
Rozważmy jakąś własność liczb naturalnych itp.
Liczba 7n-1 dzieli się przez 6.
48 342
71-1=6 72-1=48 =8 73-1=342 =57 itd. aż nam się znudzi.
6 6
Inny sposób:
I. dzieli się przez 6
71-1=6
II. Jeżeli 6 dzieli 7n-1 to 6 dzieli też -1
co kończy dowód.
7n �ą1
Dowód indukcyjny składa się z dwóch kroków:
I. Krok początkowy: sprawdzamy, że W(1) zachodzi.
W śąnźą�! W śąn�ą1źą
II. Przejście indukcyjne: sprawdzamy wynikanie . Dla każdego
ustalonego n.
Twierdzenie: 7n-1 dzieli się przez 6.
Dowód:
I. dzieli się przez 6.
71-1
II. Załóżmy, że dla każdego ustalonego n 7n-1 dzieli się przez 6. Pokażemy, że
dzieli się przez 6.
7n �ą1-1
Rzeczywiście -1=7n"7-1=ż 7śą7n-1źą�ą7-1=7śą7n-1źą�ą6.
7n �ą1
Ponieważ z założenia indukcyjnego 7n-1 dzieli się przez 6, więc -1
też.
7n �ą1
Zadanie o wieżach hanoiskich.
Ile ruchów trzeba wykonać do
przeniesienia n krążków?
H =1
1
H =3
2
H =7
3
H =15
4
itd.
1,3,7 ,15 ,31,63 ,... ,2n-1
H = f śą H źą
n�ą1 n
H
n
H =2Hn�ą1
n�ą1
Dowód:
H =2n-1
I.
n
II. Załóżmy, że dla ustalonego n
. Pokażemy, że
H =2n-1
n
H
n
również dla n+1 H =2n�ą1-1
�ą1
n�ą1
Rzeczywiście
ind
H =2Hn�ą1= 2śą2n-1źą�ą1
n�ą1
2n�ą1-2�ą1=2n�ą1-1
H
n
�ą1
H
n
Zadanie: Na ile obszarów n prostych (w położeniu ogólnym1) dzieli płaszczyznę?
r1=2 r2=4 r3=7 r4=11 r5=16
n
rn�ą1=rn�ąśąn�ą1źą rn=1�ą
śą źą
2
r1=1�ą1 r2=1�ą3 r3=1�ą6 r4=1�ą10 r5=1�ą15
Dowód:
1�ą1
r=2=1�ą zgadza się
śą źą
I.
2
n�ą1 n�ą2
rn=1�ą . rn�ą1=1�ą .
II. Załóżmy, że dla ustalonego Pokażemy, że
śą źą śą źą
2 2
Dowód wynikania:
n�ą1 n�ą1 n�ą1 n�ą2
rn�ą1=rn�ąśąn�ą1źą=1�ą �ąn�ą1=1�ą �ą =1�ą
śą źą śą źą śą źą śą źą
2 2 1 2
Ciąg Fibonacciego:
F =F =1 Fn�ą 2=F �ąF
1 2 n n�ą1
1,1,2 ,3 ,5,8,13,21 ,34 ,55,89 ,144 ,377 , ...
3 5 8 13 21
1,2 , , , , , , ...-stosunek kolejnych wyrazów
2 3 5 8 13
n n
1 1�ą 5 1-ćą
5
ćą
F = -
n
śą źą śą źą
[ ]
2 2
5
ćą
F F
n�ą1
n�ą2 n
an= F F =Fn �ąF /: F =1�ą
Fn n�ą2 �ą1 n n�ą1 F F
n�ą1 n�ą1
1 1 1 1ą 5
ćą
a �ą an �ą1=1�ą Śą a=1�ą a2=a�ą1 a2-a-1=0 a=
an a a 2
Rozwiązywanie równań rekurencyjnych II rzędu
an�ą2=Kan �ą1�ąLan
f =3 f =21 f =3f -2f
f =rn
Przykład: . Załóżmy, że istnieje (gdzie r-
1 2 n�ą1 n�ą1 n
n
rn�ą2=3rr�ą1-2rn /: rn r2=3r-2 r2-3r�ą2=0 r1=1, r2=2.
stała). Wówczas A
atwo
śą1źą f =3f -2f
f =2n
sprawdzić, że ciągi oraz f =1n spełniają warunek .
n�ą2 n �ą1 n
n n
Zauważmy, że zbiór wszystkich ciągów spełniających (1) jest przestrzenią liniową. Skoro
1 Położenie normalne  nie ma prostych równoległych ani punktów potrójnych.
f =2n
rekurencja zależy od dwóch poprzedników to wymiar jest równy 2. Zauważmy, że
n
f =1
oraz są rozwiązaniami liniowymi niezależnymi, a więc bazą. Zatem każde
n
rozwiązanie ma postać f = A"2n�ą B"1. Współczynniki A,B dobieramy z warunków
n
początkowych.
A"2�ąB=3 A=9
f =9"2n-15
Zatem
n
A"4�ąB=21 B=-15
ALGORYTM ROZWI
ZYWANIA REKURENCJI
f = Kf �ąLf
dla dwóch pierwiastków rzeczywistych równania charakterystycznego.
n�ą2 n�ą1 n
f =rn
I. Niech .
n
n�ą1
Zapisujemy równanie rn�ą2=Kr �ąLrn , po skróceniu �! równanie
r2=Kr �ąL
charakterystyczne.
r1`"r2.
II. Znajdujemy pierwiastki
f = Arn�ą Brn.
III. Zapisujemy rozwiązanie ogólne
n 1 2
IV. Wyznaczamy A,B na podstawie warunków początkowych.
Modyfikacja algorytmu dla pierwiastków wielokrotnych:
f = Kf �ąLf
Jeżeli r jest dwukrotnym pierwiastkiem równania to bazą rozwiązań są
1 n�ą2 n�ą1 n
2,
r2 oraz nr2
i dalej bez zmian (dla pierwiastków potrójnych: r2,nr1 n2 rn , itd.)
1 1 1 1
Przypadek pierwiastków zespolonych
Zadanie: Oblicz
2 2 0 0 0 �" 0
2 2 0 0 �" 0 2 2 0 0 �" 0
2 2 2 0 0 �" 0
2 2 2 0 �" 0 0 2 2 0 �" 0
0 2 2 2 0 �" 0
Dn= =2 =Żą
�" �" �" �" �" �" -2
�" �" �" �" �" �"
�" �" �" �" �" �" �"
0 �" 0 2 2 2 0 �" 0 2 2 2
#" #" #" #"
0 0 �" 0 2 2 2
#" #"
0 �" 0 0 2 2 0 �" 0 0 2 2
0 0 �" 0 0 2 2
2 2 0 0 �" 0 2 2 0 0 �" 0
�" �" �" �" �" �" �" �" �" �" �" �"
2 -2"2 =2Dn -1-4Dn-2
0 �" 0 2 2 2 0 �" 0 2 2 2
#" #" #" #"
0 �" 0 0 2 2 0 �" 0 0 2 2
2 2
D1=#"2#"=2 D2= Dn�ą2=2Dn�ą1-4Dn d =rn rn�ą 2=2rn�ą1-4rn /:rn
n
#" #"
2 2
r2=2r-4 r2-2r�ą4=0
Z rozwinięcia znajdujemy dwa niezależne rozwiązania rzeczywiste.
śą1�ą 3źąn
ćą
!śą1�ą 3źąn oraz ! śą1�ą 3źąn
ćą ćą
n n ąą n ąą
ąą ąą
1�ą 3=2śącos �ąi"sin źą śą1�ą 3źą =2nśącos �ąi"sin źą
ćą ćą
3 3 3 3
n ąą n ąą
d =A"2n"cos �ąB"2n"sin
Zatem rozwiniecie ogólne . Z warunków
n
3 3
ąą ąą nąą n ąą
2"A"cos �ą B"2"sin =1 A=1 d =2n cos �ą1 sin
n
[ ]
3 3 3 3
3
ćą
początkowych:
2 ąą 2 ąą
4"A"cos �ąB"4"sin =1 B=1
3 3
3
ćą