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