LOGIKA I MATEMATYKA DYSKRETNA
LISTA ZADA NR 7
1. Rozwi¡» zale»no±¢ rekurencyjn¡: A
n
+ A
n−1
= 2 + n
, z warunkami: A
1
= 4
, A
2
= 1
.
2. Rozwi¡» zale»no±¢ rekurencyjn¡: B
n
= (B
n−1
+ B
n−2
)/2
, z warunkami: B
1
= 0
, B
2
= 2
.
3. Rozwi¡» zale»no±¢ rekurencyjn¡: C
n
= 6C
n−1
− 9C
n−2
, z warunkami: C
1
= 3
, C
2
= 0
.
4. Oszacuj D
n
dla D
n
= 3D
n/2
+ n
√
n
.
5. Oszacuj E
n
dla E
n
= 16E
n/2
+ n
3
.
6. Jak na czas rozwi¡zywania problemu wie»y Hanoi wpªyn¦ªoby dodanie czwartego sªupka ? Je±li
nie potrasz znale¹¢ dokªadnej odpowiedzi, podaj chocia» oszacowanie z góry.
Grzegorz Kondrat