Jagiellonian University
Theoretical
Computer Science
Matematyka Dyskretna
Wykład 04
WSZIB
Edward Szczypka
szczypka@tcs.uj.edu.pl
zima 2013
Edward Szczypka
1 / 1
Jagiellonian University
Theoretical
Computer Science
Dzisiejszy wykład
Edward Szczypka
2 / 1
Jagiellonian University
Theoretical
Computer Science
spis
Edward Szczypka
3 / 1
Jagiellonian University
Theoretical
Computer Science
Poj ˛ecie Algorytmu
Algorytm
to sformalizowany sposób post ˛epowania przy rozwi ˛
azywaniu jakiego´s problemu.
Klasyczny przykład – przepisy kulinarne, instrukcje obsługi rozmaitych urz ˛
adze ´n
Algorytm:
pobiera dane wej´sciowe
wykonuje pewne (z góry przewidziane) operacje
daje dane wyj´sciowe
Pojecie danych mo˙zna rozumie´c bardzo szeroko
Algorytm powinien działa´c
poprawnie – tzn. zwraca´c zawsze poprawna odpowiedz
sko ´nczenie długo – nie powinien si ˛e p ˛etli´c
odpowiedz powinien zwraca´c w mo˙zliwie krótkim
anga˙zuj ˛
ac mo˙zliwie mało zasobów – np. pami ˛eci
Edward Szczypka
4 / 1
Jagiellonian University
Theoretical
Computer Science
Algorytm vs Program
Program
to algorytm zapisany w jakims jezyku (programowania).
program ma zwykle postac ciagu polecen, które nalezy wykonywac po kolei (chyba, ze w
samym programie przewidziana jest zmiana kolejnosci)
ten sam algorytm mozna zapisac w róznych jezykach, zwykle na wiele sposobów
Przykład 1 Algorytm ustawiania zadanej stacji w radiu:
1) Dowiedz sie, na jakiej czestotliwosci nadaje Twoja ulubiona stacja. (To sa dane wejsciowe.)
2) Nacisnij piaty guzik w siódmym rzedzie.
3) Wpisz czestotliwosc na klawiaturze.
4) Nacisnij zielony guzik pod fioletowa gałka.
5) Teraz powinno grac. (To jest rezultat - dane wyjsciowe.)
Edward Szczypka
5 / 1
Jagiellonian University
Theoretical
Computer Science
Algorytm vs Program
Rozwiazywanie równania kwadratowego:
Oznacz współczynniki równania symbolami a, b, c. (Dane wejsciowe.)
Policz ∆ = b
2
− 4ac.
Je´sli ∆ < 0, to koniec – nie ma pierwiastków rzeczywistych.
Je´sli ∆ = 0, to policz x
1
=
x
2
= −
b/2a.
Je´sli ∆ > 0, to policz x
1
=
−b+
√
∆
2a
i x
2
=
−b−
√
∆
2a
.
Program realizuj ˛
acy ten algorytm zapisany w pseudo-Pascalu:
read(a, b, c)
delta:=b*b-4*a*c
if delta<0 then
write(’Nie ma pierwiastków rzeczywistych’)
halt
if delta=0 then
x1:=-b/(2*a)
x2:=-b/(2*a)
if delta > 0 then
x1:=(-b+sqrt(delta))/(2*a)
x2:=(-b-sqrt(delta))/(2*a)
write(x1, x2)
Edward Szczypka
6 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle
Prawie kazdy wiekszy algorytm musi powtarzac pewne obliczenia, az do uzyskania jakiegos
rezultatu.
Taka sytuacja nazywana jest petla.
Typowa (i jedyna potrzebna tutaj) petla to:
WHILE
warunek DO polecenie
Taka petla:
sprawdza podany warunek
i jesli jest spełniony, to wykonuje podane polecenie
nastepnie ponownie sprawdza warunek
(wartosci dla których warunek jest sprawdzany mogły ulec zmianie przez wykonanie
polecenia)
i jesli jest spełniony, to wykonuje podane polecenie
nastepnie ponownie sprawdza warunek
i jesli jest spełniony, to wykonuje podane polecenie
. . .
. . .
Wyjscie z petli nastepuje wiec wtedy, gdy warunek nie jest spełniony
bo albo w ogóle nie był spełniony,
albo przestał byc spełniony na skutek wykonywania polecenia
Edward Szczypka
7 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle - graficznie
Edward Szczypka
8 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle – przykłady
Przykład 2 Wypisanie liczb od 1 do 100:
write(’Zaczynamy’)
x := 1
while x <= 100 do
write(x)
x := x + 1
write(’I to by było na tyle’)
W tym programie nie ma danych wej´sciowych.
Dane wyj´sciowe to wypisane liczby 1, 2, . . . , 100 (oraz ew. komentarze tekstowe).
Bardzo typowe jest podstawienie x := x + 1. Jego sens jest taki: zwi ˛eksz x o jeden.
Przykład 3 A co robi program?
read(a)
write(’Zaczynamy’)
x := 1
while x <= a do
x := x + 1
write(x)
write(’I to by było na tyle’)
Edward Szczypka
9 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle - problemy
P˛etle s ˛
a bardzo silnym narz ˛edziem programistycznym, ale mog ˛
a by´c powodem wielu komplikacji.
Istotne pytania to:
1
Czy algorytm/procedura zako ´nczy si ˛e?
2
Czy po zako ´nczeniu daje poprawne wyniki?
3
Jak długo trwa wykonanie procedury?
4
Ile pami ˛eci zu˙zywa procedura?
Do analizowania dwu pierwszych problemów słu˙z ˛
a tzw.
NIEZMIENNIKI P ˛
ETLI
.
Edward Szczypka
10 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle - Niezmienniki
W p ˛etli WHILE W DO S
W
jest warunkiem – formuła logiczna, od spełnienia której zale˙zy wykonywanie p ˛etli
S
jest lista czynno´sci wykonywanych w p ˛etli
NIEZMIENNIKIEM
p ˛etli WHILE W DO S jest
warunek (formuła logiczna) P taki, ze:
je´sli W ∧ P zachodzi przed wykonaniem czynno´sci S
to P zachodzi po wykonaniu czynno´sci S.
U ˙
ZYTECZNA OBSERWACJA:
Je´sli:
P jest niezmiennikiem p ˛etli WHILE W DO S
P jest spełniony przy wej´sciu w te p ˛etle
to:
w ka˙zdym takcie p ˛etli warunek P jest spełniony
przy wyj´sciu z p ˛etli warunek P jest spełniony, a W juz nie.
Edward Szczypka
11 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle – Niezmienniki – Graficznie
Edward Szczypka
12 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle – Liczenie Silni
INPUT: a<= 0
OUTPUT: s = a!
INITIAL:
s:=1
x:=1
WHILE x<a DO x:=x+1
s:=s*x
END
Edward Szczypka
13 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle - Liczenie Silni
Edward Szczypka
14 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle – Liczenie Silni – Analiza
Potrzebujemy wykaza´c, ˙ze po wyj´sciu z p ˛etli rzeczywi´scie s = a!. Najpierw pokazujemy, ze
niezmiennikiem petli jest warunek (s = x ! i x ¬ a): Skoro jest on spełniony przed wej´sciem w
p ˛etle, to mamy:
x
stare
<
a
s
stare
=
x
stare
!
i x
stare
¬ a
Czynno´sci p ˛etli zmieniaj ˛
a warto´sci x i s na:
x
nowe
=
x
stare
+
1
s
nowe
=
s
stare
x
nowe
=
s
stare
(
x
stare
+
1)
sk ˛
ad s
nowe
=
s
stare
(
x
stare
+
1) = x
stare
!(
x
stare
+
1) = (x
stare
+
1)! = x
nowe
!
Nadto, skoro x
stare
<
a
to
x
nowe
=
x
stare
+
1 ¬ a.
Z kolei przy wyj´sciu z p ˛etli mamy:
x > a
s = x ! i x ¬ a
co daje x = a oraz s = x ! = a!.
Edward Szczypka
15 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle – Liczenie Silni – inne liczenie Silni
INPUT: a <= 0
OUTPUT: s = a!
INITIAL:
s:=1
x:=a
WHILE x>0 DO s:=s*x
x:=x-1
END
Edward Szczypka
16 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle – Liczenie Silni – inne liczenie Silni
Uzasadnij, ze:
wyra˙zenie podane w nawiasie jest rzeczywi´scie niezmiennikiem p ˛etli,
oraz gwarantuje poprawno´s´c wyniku tzn., ze przy wyj´sciu z p ˛etli s = a!.
Edward Szczypka
17 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle i niezmienniki – Problem Stopu
INPUT: a <= 0
OUTPUT: ?
INITIAL: x:=a
WHILE x<>8 DO PRINT x^2
x:=x+2
END
Co robi powy˙zsza procedura i kiedy si ˛e zatrzymuje (dla jakich warto´sci a)?
Zauwa˙z, ze kolejno´s´c instrukcji w prostok ˛
acie jest istotna!
Edward Szczypka
18 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle i niezmienniki – Nierozwi ˛
azany Problem Stopu
INPUT: a >= 0
OUTPUT: ?
INITIAL: x:=a
WHILE x<>1 DO
IF x jest parzyste THEN
x:=x/2
ELSE
x:=3*x+1
END
Narysuj schemat blokowy tej procedury. Spróbuj znale´z´c niezmienniki p ˛etli. Spróbuj uzasadni´c,
˙ze zawsze si ˛e zatrzyma – na jakie kłopoty natrafiasz?
Ta procedura wygl ˛
ada na do´s´c prosta,
ale . . .
do dzi´s nie wiadomo, czy zawsze si ˛e zatrzymuje . . .
Edward Szczypka
19 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle i niezmienniki – dzielenie z reszt ˛
a
INPUT: liczby naturalne a >= 0, b > 0
OUTPUT: liczby naturalne q i r takie, ze a = qb + r oraz 0 <= r < b
INITIAL:
q:=0
r:=a
WHILE r>=b DO
r:=r-b
q:=q+1
END
Edward Szczypka
20 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle i niezmienniki – dzielenie z reszt ˛
a – analiza
Poka˙zemy, ze niezmiennikiem jest warunek:
0 ¬ r
i a = qb + r
Wtedy, przy wyj´sciu z p ˛etli mamy:
r < b
0 ¬ r i a = qb + r
czyli dokładnie nało˙zone przez nas warunki: a = qb + r oraz 0 ¬ r < b.
Spełnienie niezmiennika przy wej´sciu w p ˛etle oznacza, ˙ze:
0 ¬ r
stare
oraz a = q
stare
· b + r
stare
Z kolei przebieg p ˛etli zmienia warto´sci r i q na:
r
nowe
=
r
stare
− b
q
nowe
=
q
stare
+
1
sk ˛
ad mamy:
q
nowe
· b + r
nowe
= (
q
stare
+
1) · b + r
stare
− b = q
stare
· b + b + r
stare
− b = q
stare
· b + r
stare
=
a
Nadto, skoro czynno´sci p ˛etli wykonuj ˛
a si ˛e, to r
stare
>
b sk ˛
ad r
nowe
=
r
stare
− b > b − b = 0.
Edward Szczypka
21 / 1
Jagiellonian University
Theoretical
Computer Science
P˛etle i niezmienniki – szybkie pot ˛egowanie
INPUT: liczby naturalne a,n >= 0
OUTPUT: liczby naturalna b=a^n
INITIAL:
b:=1
x:=a
i:=n
WHILE i>0 DO
IF i jest nieparzyste THEN
b:=b*x
i:=(i-1)/2
ELSE
i:=i/2
x:=x*x
END
Narysuj schemat blokowy tego algorytmu.
Wykaz, ze niezmiennikiem p ˛etli jest x
i
· b = a
n
.
U˙zyj tego faktu do pokazania, ze ta procedura działa poprawnie.
Jaki inny warunek nale˙zy w tym celu umie´sci´c w niezmienniku?
Edward Szczypka
22 / 1
Jagiellonian University
Theoretical
Computer Science
spis
Edward Szczypka
23 / 1
Jagiellonian University
Theoretical
Computer Science
Liczby Naturalne – zasada indukcji
Liczby naturalne s ˛
a bardzo wa˙zne w praktyce programistycznej ˝
O s ˛
a u˙zywane do
kodowania (implementowania) danych,
adresowania pami ˛eci,
taktowania programów,
Jedna z podstawowych ich własno´sci jest to, ˙ze do ka˙zdej z nich mo˙zna ¯
ddoj´s´c ˝u zaczynaj ˛
ac od
zera i dodaj ˛
ac 1 odpowiednio wiele razy. Oznacza to, ze
jesli: A ⊆ N jest jakim´s zbiorem liczb naturalnych,
– w którym jest zero
tzn. 0 ∈ Z
– wraz z pocz ˛
atkiem ka˙zdego "kroku"
tzn. ∀k ∈ A k + 1 ∈ A
jest w nim i jego koniec
to: A zawiera juz w sobie WSZYSTKIE liczby naturalne, tzn. A = N.
Edward Szczypka
24 / 1
Jagiellonian University
Theoretical
Computer Science
Zasada indukcji – Przykłady
Przykład 1 Niech zbiór Z składa si ˛e z tych liczb naturalnych n, dla których suma liczb
naturalnych nie przekraczaj ˛
acych n wynosi
n+a
2
, tzn. spełniaj ˛
acych
0 + 1 + 2 + . . . + n =
n(n + 1)
2
Czy Z = N? tzn. czy wszystkie liczby naturalne maja powy˙zsza własno´s´c? Oczywi´scie 0 ∈ Z , bo
suma liczb naturalnych nie przekraczaj ˛
acych zera to 0 =
0(0+1)
2
Nadto, gdy k ∈ Z , tzn.
0 + 1 + 2 + . . . + k =
k (k + 1)
2
to, badaj ˛
ac, czy k + 1 ∈ Z rozwa˙zamy sum ˛e
0 + 1 + 2 + . . . + k + (k + 1)
=
(
1 + 2 + 3 + . . . + k ) + (k + 1)
=
k (k + 1)
2
+ (
k + 1) =
k (k + 1) + 2(k + 1)
2
=
(
k + 1)(k + 2)
2
=
(
k + 1)((k + 1) + 1)
2
co ´swiadczy o tym, ˙ze k + 1 ∈ Z .
Edward Szczypka
25 / 1
Jagiellonian University
Theoretical
Computer Science
Zasada indukcji – Przykłady
Przykład 2
Z =
n
n ∈ N : 0
2
+
1
2
+
3
2
+ . . . +
n
2
=
n(n + 1)(2n + 1)
6
o
Je´sli poka˙zemy, ze Z = N to dostaniemy ładny wzór na sum ˛e kolejnych kwadratów
Oczywi´scie 0 ∈ Z ,
Nadto, gdy k ∈ Z , to aby stwierdzi´c czy k + 1 jest w Z rozwa˙zamy sum ˛e
0
2
+
1
2
+
2
2
+ . . . +
k
2
+ (
k + 1)
2
=
(
0
2
+
1
2
+
2
2
+ . . . +
k
2
) + (
k + 1)
2
=
k (k + 1)(2k + 1)
6
+ (
k + 1)
2
=
k (k + 1)(2k + 1)
6
+ (
k + 1)
2
=
k (k + 1)(2k + 1) + 6(k + 1)
2
6
=
(
k + 1)(k (2k + 1) + 6(k + 1))
6
=
(
k + 1)(2k
2
+
7k + 6)
6
=
(
k + 1)((k + 2)(2k + 3))
6
=
(
k + 1)((k + 1) + 1)(2(k + 1) + 1)))
6
co ´swiadczy o tym, ˙ze k + 1 ∈ Z .
Edward Szczypka
26 / 1
Jagiellonian University
Theoretical
Computer Science
Zasada indukcji – Przykłady
Przykład 2 Liczenie sumy pot ˛eg kolejnych liczb naturalnych ma bezpo´sredni zwi ˛
azek z praktyka
programistyczna.
Je´sli dla danych wielko´sci k wykonanych musi by´c k
s
operacji, a w programie jest p ˛etla
wykonuj ˛
aca te operacje dla k = 0, 1, 2, 3, . . . az do n, to ł ˛
acznie wykonanych jest Σ
n
k =0
k
s
operacji
Widzieli´smy ju˙z, ˙ze:
Σ
n
k =0
k
=
n(n + 1)
2
Σ
n
k =0
k
2
=
n(n + 1)(2n + 1)
6
Edward Szczypka
27 / 1
Jagiellonian University
Theoretical
Computer Science
Zasada indukcji – Sumowanie pot ˛eg liczb naturalnych
Zadanie 3 Poka˙z, ˙ze:
Σ
n
k =0
k
3
=
n
2
(
n + 1)
2
2
Σ
n
k =0
k
4
=
n(n + 1)(2n + 1)(3n
2
+
3n − 1)
30
Σ
n
k =0
k
5
=
n
2
(
n + 1)
2
(
2n
2
+
2n − 1)
12
Σ
n
k =0
k
4
=
n(n + 1)(2n + 1)(3n
4
+
6n
3
− 3n + 1)
42
Σ
n
k =0
k
7
=
n
2
(
n + 1)
2
(
3n
4
+
6n
3
− n
2
− 4n + 2)
24
Σ
n
k =0
k
8
=
n(n + 1)(2n + 1)(5n
6
+
15n
5
+
5n
4
− 15n
3
− n
2
+
9n − 3)
90
Edward Szczypka
28 / 1
Jagiellonian University
Theoretical
Computer Science
Zasada indukcji – Sumowanie pot ˛eg liczb parzystych
Czasem sumujemy tylko co druga liczb ˛e.
Oczywi´scie sumowanie dla liczb parzystych jest łatwiejsze, bo na przykład:
Σ
n
k =0
2k = 2Σ
n
k =0
k = k (k + 1)
Σ
n
k =0
(
2k )
2
=
4Σ
n
k =0
k =
2n(n + 1)(2n + 1)
3
Σ
n
k =0
(
2k )
3
=
8Σ
n
k =0
k = 2n
2
(
n + 1)
2
Zadanie 4 Policz;
Σ
n
k =0
(
2k )
4
=
?
Σ
n
k =0
(
2k )
5
=
?
Σ
n
k =0
(
2k )
6
=
?
Σ
n
k =0
(
2k )
7
=
?
Σ
n
k =0
(
2k )
8
=
?
Edward Szczypka
29 / 1
Jagiellonian University
Theoretical
Computer Science
Zasada indukcji – Sumowanie pot ˛eg liczb nieparzystych
Przykład 5 A ile wynosi suma kolejnych liczb nieparzystych;
Σ
n
k =1
(
2k − 1) =?
Oczywi´scie
Σ
n
k =1
(
2k − 1) = 2
X
k = 1nk −
X
k = 1n1 = 2
n(n + 1)
2
− n = n(n + 1) − n = n
2
Przykład 6 Łatwo sprawdzi´c, ze wzór
Σ
n
k =1
(
2k − 1)
2
=
n(4n
2
− 1)
3
zachodzi dla n = 0.
Nadto
Σ
n+1
k =1
(
2k − 1)
2
=
X
k = 1n(2k − 1)
2
+ (
2(n + 1) + 1)
2
=
n(4n
2
− 1)
3
+
3(2n + 1)
2
3
=
4n
3
+
12n
2
+
11n + 3
3
=
(
n + 1)(4(n + 1)
2
− 1))
3
Edward Szczypka
30 / 1
Jagiellonian University
Theoretical
Computer Science
Zasada indukcji – Sumowanie pot ˛eg liczb nieparzystych
Poza wzorami
Σ
n
k =1
(
2k − 1)
=
n
2
Σ
n
k =1
(
2k − 1)
2
=
n(4n
2
− 1)
3
mamy
Zadanie 7 Poka˙z, ˙ze:
Σ
n
k =1
(
2k − 1)
3
=
n
2
(
2n
2
− 1)
Σ
n
k =1
(
2k − 1)
4
=
n(4n
2
− 1)(12n
2
− 7)
15
Σ
n
k =1
(
2k − 1)
5
=
n
2
(
16n
4
− 20n
2
+
7)
3
Σ
n
k =1
(
2k − 1)
6
=
n(4n
2
− 1)(48n
4
− 72n
2
+
31)
21
Edward Szczypka
31 / 1
Jagiellonian University
Theoretical
Computer Science
Zasada indukcji – Modyfikacje
Jesli nasz "marsz"
zamiast od zera zaczniemy od innej liczby a,
ale upewnimy si ˛e, ze zbiór Z ⊆ N, tak jak uprzednio wraz z ka˙zd ˛
a liczb ˛
a k , b ˛edzie zawierał
jej nast ˛epnik k + 1
to mo˙zemy wnioskowa´c, ˙ze w Z s ˛
a wszystkie liczby naturalne pocz ˛
awszy od a, tzn. je´sli
a ∈ Z ⊆ N i ∀k ∈ Z
k + 1 ∈ Z
to Z = {n ∈ N : n a}.
Inna modyfikacja jest zakładanie, ze zbiór Z ⊆ N spełnia:
0 ∈ Z
Z zawiera jak ˛
a´s liczb ˛e, je ˛eli tylko zawiera wszystkie mniejsze od niej
o którym to zbiorze tez mo˙zemy wnioskowa´c, ˙ze Z = N.
Na ogół łatwiej jest wywnioskowa´c, ze k + 1 ∈ Z wiedz ˛
ac, ze 0, 1, 2, . . . , k ∈ Z , ni˙z wiedz ˛
ac
tylko, ˙ze k ∈ Z .
Edward Szczypka
32 / 1
Jagiellonian University
Theoretical
Computer Science
Zasada indukcji – Nierówno ´sci
Mamy przeczucie, ze funkcja n
2
ro´snie wolniej ni˙z 2
n
. Co prawda dla pocz ˛
atkowych warto´sci
mamy
n
0
1
2
3
4
5
6
7
8
. . .
n
2
0
1
4
9
16
25
36
49
64
. . .
2
n
1
2
4
8
16
32
64
128
256
. . .
i zachowanie tych dwu funkcji nie jest "zdecydowane", ale juz od wi ˛ekszych warto´sci 2
n
znacznie
dominuje n
2
. Aby si ˛e przekona´c, ˙ze;
n
2
<
2
n
dla n 5
przeprowad´zmy dowód indukcyjny:
Poka˙zemy najpierw, ˙ze 2n + 1 < 2
n
(dla zupełnie dowolnego n 3)
oczywi´scie 2 · 3 + 1 = 7 < 8 = 2
3
oraz 2(n + 1) + 1 = 2n + 3 < 2
n
+
4 = 2
n
+
2
2
<¬
2
n
+
2
n
=
2 · 2
n
=
2
n+1
a nast ˛epnie
zauwa˙zmy, ˙ze 5
2
=
25 < 32 = 2
5
,
oraz, ˙ze (n + 1)
2
=
n
2
+ (
2n + 1), 2
n
+
2
n
=
2 · 2
n
=
2
n+1
Edward Szczypka
33 / 1
Jagiellonian University
Theoretical
Computer Science
Zasada indukcji – Nierówno ´sci
Podobnie, aby pokaza´c, ˙ze:
n
3
<
2n
dla n 10
pokazujemy kolejno, ˙ze:
6n + 6 < 2
n
ju˙z dla n > 6
to mo˙zna pokaza´c podobnie jak uprzednio 2n + 1 < 2
n
,
3n
2
+
3n + 1 < 2
n
dla n 10
jako, ˙ze 3 · 10
2
+
3 · 10 + 1 = 331 < 1024 = 210
oraz
3(n + 1)
2
+
3(n + 1) + 1 = (3n
2
+
3n + 1) + (6n + 6) < 2
n
+
2
n
=
2 · 2
n
=
2
n+1
a nast ˛epnie:
nierówno´s´c 10
3
=
1000 < 1024 = 2
10
wraz z (n + 1)
3
=
n
3
+ (
3n
2
+
3n + 1) < 2
n
+
2
n
=
2
n+1
Zadanie 8 Pokaz, ze dla dowolnego wykładnika c mamy
n
c
<
2n
dla dostatecznie du˙zych liczb naturalnych n.
Edward Szczypka
34 / 1
Jagiellonian University
Theoretical
Computer Science
Zasada indukcji – Arytmetyka Modularna
Przykład 9 Poka˙zemy, ze 2|n
2
− n.
Istotnie 0
2
− 0 = 0 = 2 · 0, czyli 0
2
− 0 jest podzielne przez 2.
Nadto, gdy n
2
− n jest podzielne przez 2 to n
2
− n = 2x dla pewnej liczby x ∈ N.
A wtedy
(
n + 1)
2
− (n + 1) = n
2
+
2n + 1 − n − 1 = (n
2
− n) + 2n = 2x + 2n = 2 · (x + n),
co oznacza, ˙ze (n + 1)
2
− (n + 1) te˙z jest podzielne przez 2.
Przykład 10 Poka˙zemy, ˙ze 6|n
3
− n.
Istotnie 0
3
− 0 = 0 = 6 · 0, czyli 0
3
− 0 jest podzielne przez 6.
Nadto, gdy n
3
− n jest podzielne przez 6 to n
3
− n = 6x dla pewnej liczby x ∈ N.
A wtedy
(
n + 1)
3
− (n + 1) = n
3
+
3n
2
+
3n + 1 − n − 1 = (n
3
− n) + 3n
2
+
3n = 6x + 3n(n + 1)
Oczywi´scie 3n(n + 1) jest podzielne przez 3. Ale n(n + 1) to iloczyn kolejnych dwu liczb,
wiec która´s z nich, (a zatem i ich iloczyn) musi by´c parzysta.
Oznacza to, ze 3n(n + 1) jest podzielne przez 6, wiec i suma 6x + 3n(n + 1) jest podzielna
przez 6. Czyli, ze (n + 1)2 − (n + 1) te˙z jest podzielne przez 6.
Edward Szczypka
35 / 1
Jagiellonian University
Theoretical
Computer Science
Zasada indukcji – Małe twierdzenie Fermata
Przykład 11 Poka˙zmy, ˙ze je´sli p jest liczba pierwsza to p|n
p
− n.
Oczywi´scie p|0 = 0
p
− 0.
Nadto
(
n + 1)
p
− (n + 1) = Σ
p
k =0
p
k
n
k
− (n + 1) = (n
p
− n) + Σ
p−1
k =1
p
k
n
k
Pierwszy składnik tej ostatniej sumy jest podzielny przez p na mocy naszego zało˙zenia
indukcyjnego.
A drugi?
Wystarczy pokaza´c, ˙ze dla k = 1, 2, . . . , p − 1 ka˙zda liczba postaci
p
k
jest podzielna przez p.
Ale
p
k
=
p!
k !(p − k )!
=
(
p − k + 1)(p − k + 2) . . . (p − 1)p
k !
Poniewa˙z p jest liczba pierwsz ˛
a, wi ˛ec ˙zeby ten ułamek był skracalny przez p, to który´s czynnik w
mianowniku musiałby by´c podzielny przez p.
A tak jest, gdy˙z wyst ˛epuj ˛
a tam tylko liczby silnie mniejsze ni˙z p, a mianowicie 1, 2, 3, . . . , k < p.
Edward Szczypka
36 / 1
Jagiellonian University
Theoretical
Computer Science
Zasada indukcji – Małe twierdzenie Fermata
Przykład 12 Poka˙zmy, ˙ze 12|10
n
− 4 dla n 2
Rzeczywi´scie 10
2
− 4 = 96 = 12 · 8 wi ˛ec 10
2
− 4 dzieli si ˛e przez 12.
Dodatkowo, skoro 12|10
n
− 4 to 10
n
− 4 = 12x, zatem mo˙zemy przedstawi´c
10
n+1
=
10 · 10
n
=
10 · 12x czyli te˙z jest podzielny przez 12.
Edward Szczypka
37 / 1