Matematyka dyskretna

zadania warte są 1 punkt

Krzysztof Misztal

07-01-2013

Zadanie 1. Rozwiąż rekurencje:

• T (n) = 4T (n − 1) + 2

n

, T (0) = 6,

• T (n) = 3T (n − 1) + n, T (0) = 10,

• T (n) = 2T (n − 1) + 2, T (0) = 1 oraz porównaj z T (n) = 3T (n − 1) + 3, T (0) = 1,

• T (n) = 2T (n − 1) + n2

n

, T (0) = 1,

• T (n) = 2T (n − 1) + n

3

2

n

, T (0) = 2,

• T (n) = rT (n − 1) + r

n

, T (0) = 1,

• T (n) = rT (n − 1) + s

n

, T (0) = 1,

Zadanie 2. Ciąg Fibonacciego dany jest wzorem

T (n) =

(

T (n − 1) + T (n − 2),

n > 1

1,

n = 0 lubn = 1

• Wypisz kolka pierwszych wyrazów ciągu

• Pokaż, że



1 +

√

5

2



n



1 −

√

5

2



n

są rozwiązaniami równania T (n) = T (n − 1) + T (n − 2).

• Czy

c

1



1 +

√

5

2



n

+ c

2



1 −

√

5

2



n

jest rozwiązaniem równania T (n) = T (n − 1) + T (n − 2) dla każdego c

1

, c

2

∈ R?

• Znajdź takie stałe c

1

, c

2

∈ R aby ciąg Fibonaciego był zadany wzorem

T (n) = c

1



1 +

√

5

2



n

+ c

2



1 −

√

5

2



n

1