egzamin z dyskretnej

07.02.2013

!mie i nazwisko

Egzamin /. matematyki dyskretnej

1.    (a) Załóżmy, że G(z) jest funkcją tworzącą dla ciągu {gk)k>o- Niecił h_k - dla k € N*. Znajdź

funkcję tworzącą H(z) ciągu [hk).

(b)    Niech gk ~ k+1 dla k € N*. Używając dowolnej (skutecznej) metody wyznacz zwartą postać funkcji tworzącej G{z) tak określonego ciągu {gk).

(c)    Korzystając z (a) i (b) znajdź zwartą postać funkcji tworzącej H(z) ciągu h o wyrazie ogólnym hk = t = 2k + 1. k 6 N*.

2.    Niech n e N oraz k 6 N*.

(a)    Uzasadnij, że równanie

+ .. - + x_n = k

ma |^{/J +} ^ różnych rozwiązań (zj, x-j, .... x„) o wszystkich współrzędnych całkowitych i nieujemnych, tzn. ę W*. Takie rozwiązania będziemy w dalszym ciągu nazywać istotnymi.

(b)    Wyznacz i zapisz w postaci sumy liczbę istotnych rozwiązań nierówności

Xi + X2 + ... + x_n < k.    (1)

Wskazówka: Potraktuj nierówność (1) jako alternatywę równań postaci XI +x₂ + ... + T„ =p, gdzie p = 0, \, ..., k.

(c)    Wykaż, że liczba Istotnych rozwiązań nierówności (1) jest równa liczbie Istotnych rozwiązań równania

*1 + *2 + ... + X_n + £_n+! = k.

Wykorzystaj ten fakt do znalezienia zwartej postaci sumy wyznaczonej w punkcie (b).

3.    Niech (/•'„) będzie ciągiem liczb Fibonacciego

(a)    Oblicz £Li F_k.

(b)    Niech b_k = F_kFk~\ dla k 6 M. Wyznacz ciąg różnic (Afr)* dla ciągu (6*).

h

(c)    Znajdź zwartą postać sumy F_k.