Matematyka dyskretna - zasada indukcji matematycznej i jej
zastosowania
Aleksandra Orpel
1
Dowodzenie twierdzeń za pomoc ¾
a indukcji
1. Udowodnić indukcyjnie wzóry na n ty wyraz ci ¾
agu geomtrycznego
oraz sum ¾
e n pierwszych wyrazów tego ci ¾
agu.
2. Udowodnić, ·
ze dla dowolnej liczby naturalnej n > 0 zachodz ¾
a
wzory
n
X
(a)
i(i + 1) = 1 n (n + 1) (n + 2) ;
3
i=1
n
X
(b)
i2 = n(n+1)(2n+1) ;
6
i=1
!
n
X
2
n
X
2
(c)
i
=
i3 =
n(n+1)
;
2
i=1
i=1
n
X
(d)
i2 (i + 2) = 1 n (n + 1) (3n2 + 11n + 4) ; 12
i=1
n
X
(e)
1
= 1 1 + 1 + 1
1
1
1
;
i(i+3)
3
2
3
n+1
n+2
n+3
i=1
n
Y
(f)
i
=
24
:
(i+4)
(n+1)(n+2)(n+3)(n+4)
i=1
3. Znajdź i udowodnij wzór opisuj ¾
acy sum ¾
e oraz iloczyn jako funkcj ¾
e
n :
n
X
(a)
1
;
i(i+2)
i=1
1
Y
(b)
i
:
(i+3)
i=1
(Wsk. porównaj z przyk÷
adami 2-e i 2-f.)
4. Udowodnić indukcyjnie nierówności (a) n! > 2n; dla n
4;
(b) 2n
n3; dla n
10;
(c) 2n > n2; dla n > 4:
5. Udowodnić nierówności
(a)
(1 + a)n
1 + na; dla a >
1:
(b)
n (n
1)
(1 + a)n
1 + an +
a2; dla a
0:
2
6. Wykazać, ·
ze dla dowolnych liczby naturalnej
(a) 3j (n3
n) ;
(b) 5j (n5
n) ;
(c) 7j (n7
n) :
7. Niech dla dowlnego n
0; an = F ib(n) Wykazać, ·
ze 2ja3n; 3ja4n
oraz 5ja5n:
8. Niech dla dowonego k 2 N dane b ¾
ed ¾
a liczby ak; bk 2 R: Udowodnić
poni·
zszy wzór dla dowolnego n
2
n 1
X
n 1
X
(ak+1
ak) bk = anbn
a1b1
ak+1 (bk+1
bk) :
k=1
k=1
9. Niech a; b 2 R; n 2 N: Dowieść indukcyjnie wzoru n
X n
(a + b)n =
an ibi:
i
i=0
2
Wykorzystanie indukcji w algorytmach zawieraj ¾
acych p ¾
etl ¾
e
1. Rozwa·
zmy ci ¾
ag instrukcji
s:=2;
i:=1;
while 1
i do
begin
wypisz s;
s:=s+2i+1;
i:=i+1;
end.
Zbadać, czy po dowolnym przebiegu p ¾
etli warunek
"s = i2 + 1"
(p)
jest spe÷
niony: Podać 1243 liczb ¾
e wypisan ¾
a przez ten algorytm?
Sprawdzić doświadczalnie poprawność odpowiedzi.
2. Rozwa·
zmy ci ¾
ag instrukcji
s:=1;
while 1
S do
begin
wypisz s;
p
s:=s+2
S +1;
end.
Pokazać, ·
ze na pocz ¾
atku n: przebiegu p ¾
etli zachodzi równość S =
n2:
3
Badanie poprawności algorytmów
- (zadania te realizowane b ¾
ed ¾
a na pierwszych zaj ¾
ecia po kolok-
wium)
1. Wyka·
z poprawność algorytmu binarnego obliczania n: pot ¾
egi liczby
a 2 Rnf0; 1g; n 2 N :
P ot ¾
ega_bin (a; n)
begin
1 z := a; y := 1; m := n;
2 while m 6= 0 do
3
begin
4
if m mod 2 = 1 then y := y z;
5
m := m div 2;
6
z := z z;
3
end;
8 wypisz "y";
end:
(Wsk. Rozwa·
zyć zdanie :" zmy = an ") 2. Wyka·
z, ·
ze algorytm
Bin(n)
begin
t := n; k := 0;
while t
1 do
begin
k := k + 1;
b[k] := t mod 2;
t := t div 2;
end;
end.
zwraca tablic ¾
e b zawieraj ¾
aca reprezentacj ¾
e binarn ¾
a liczby n poczy-
naj ¾
ac od najmniej znacz ¾
acych bitów. Zak÷
adamy, ·
ze na pocz ¾
atku
tablica b zosta÷
a wyzerowana. (Wsk. Rozwa·
zyć zdanie
"Je·zeli tablica b jest reprezentacj ¾
a binarn ¾
a liczby naturalnej m
(rozpoczynaj ¾
ac od najmniej znacz ¾
acych bitów); to n = t 2k + m:"
3. Zadaniem poni·
zszego algorytmu jest wyznaczenie cz ¾
esci ca÷
kowitej
q i reszty r dzielenia liczby ca÷
kowitej m
0 przez liczb ¾
e naturaln ¾
a
n :
Dzielenie(m; n)
begin
q := 0;
r := m;
while r
n do
begin
q := q + 1;
r := r
n;
end;
end:
Zbadać poprawność tego algorytmu.
(Wsk.
Rozwa·
zyć zdanie:
"m = nq + r ^ r
0")
4. Sprawdź, czy poni·
zszy algorytm wyznacza n!
Silnia_1(n)
Dane wejściowe: n 2 N:
Dane wyjściowe: liczba naturalna silnia = n!.
4
silnia := 1;
m := n;
while m > 0 do
begin
silnia := silnia m;
m := m
1;
end;
end:
(Wskazówka: rozwa·
z zdanie "silnia m! = n!":) 5. Sprawdź, czy dla dowolnej liczby naturalnej n nast ¾
epuj ¾
acy algo-
rytm wyznacza wartości n!:
Silnia_1(n)
Dane wejściowe: n 2 N:
Dane wyjściowe: liczba naturalna silnia = n!.
begin
silnia := 1;
m := 1;
while m
n do
begin
silnia := silnia m;
m := m + 1;
end;
end:
6. Zadaniem poni·
zszego algorytmu jest rozk÷
ad liczby naturalnej n
na iloczyn liczby nieparzystej i pot ¾
eg ¾
e liczby 2:
Rozklad(n)
Dane wejściowe: liczba naturalna n: Dane wyjściowe: liczby nieujemne m i k takie, ·ze m jest nieparzysta i n = m 2k:
begin
m := n;
k := 0;
while (m jest liczba parzysta) do
begin
m := m=2;
k := k + 1;
end;
end:
Zbadaj poprawność algorytmu Rozklad.
5
zmy nast ¾
epuj ¾
acy algorytm, którego zadaniem jest sprawdze-nie, czy dana liczba naturalna n jest liczb ¾
a pierwsz ¾
a:
prime (n)
p:=2; B:=true;
while (p< n ^ B) do
begin
if n mod p=0 then B:=false;
p := p + 1;
end;
if B then wypisz "Dana liczba jest liczb ¾
a pierwsz ¾
a"
else wypisz "Dana liczba nie jest liczb ¾
a pierwsz ¾
a"
Sprawdź poprawność tej procedury.
8 Zbadać poprawność procedury
Partition (X, Left, Right);
Dane wejściowe: tablica X o ró·znych elementach, X[Left..Right]; Dane wyjściowe: tablica X oraz indeks Midddle taki, ·ze dla ka·zdego i
M iddle : X[i]
X[M iddle] oraz X[j] > X[M iddle] dla wszystkich j>Middle;
1begin
2
pivot:=X[Left];
3
L:=Left; R:=Rihgt;
4
while L<R do
5
while (X[L]
pivot and L Right) do L:=L+1;
6
while (X[R] > pivot and R Left) do R:=R-1; 7
if L<R then
8
zamień X[L] z X[R];
9
Middle:=R;
10
zamień X[Left] z X[Middle]
11end.
(Literatura: Manber U., Introduction to Algorithms, Addison-Wesley Publishing Company, New York, 1989.) 9 Rozwa·
zmy nast ¾
epuj ¾
ac ¾
a procedur ¾
e:
Lomuto_Partition(A,1,n)
x:=A[n]; i:=0; j:=1;
while j
n do
begin
if A[j] x then
6
begin i:=i+1; zamień A[j] z A[i] end; j:=j+1;
end;
if i<n then return i ;
else return i-1.
Zadaniem tej procedury jest przestawienie elementów A[1]; :::; A[n]
w taki sposób, aby ka·
zdy element w obszarze A[1::i] by÷mniejszy lub równy x = A[n], a ka·
zdy element w drugim obszarze A[i + 1::n] by÷wi ¾
ek-
szy ni·
z x. Sprawdź poprawność procedury. (Literatura: T.H.Cormen & Ch.E.Leiserson & R.L. Rivest "Wprowadzenie do algorytmów "; Wydawnictwo Naukowo-Techniczne, Warszawa, 2001) 7