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