zad MD 2015 I 6

Olsztyn, dn. 31.03.2015 r.

Matematyka dyskretna, seria 6 (zależności rekurencyjne)

Zad 1. Niech t_n oznacza liczbę różnych sposobów wejścia po schodach zbudowanych z n stopni, jeśli w każdym kroku można pokonać jeden lub dwa stopnie. Wykazać, że ciąg t_n można wyznaczyć z rekurencji

t_n = t_n-1 + t_n_2    dla n > 3, t\ 1, t₂ = 2.

Zad 2. Przypiszmy kropce w kodzie Morse’a długość jeden, a kresce długość dwa. Przez długość zdania kodowego rozumiemy sumę długości wszystkich kropek i kresek w zdaniu. Wyznaczyć zależność rekurencyjną dla liczby zdań długości n € N.

Zad 3. Sprawdzić bezpośrednim rachunkiem, że wyznaczona na ćwiczeniach liczba d_n nieporządków rzędu n spełnia zależność rekurencyjną

d_n = (n- l)d„_i + (n - l)d„_₂.

Zad 4. Niech p_n będzie liczbą podziałów zbioru {1,2,____, n} na dwa niepuste

zbiory. Znaleźć zależność rekurencyjną dla p_n oraz wypisując kilka, pierwszych wartości spróbować zgadnąć rozwiązanie tej rekurencji.

Zad 5. Niech ciąg f_n spełnia równanie rekurencyjne

fn = fn-1 + fn-2,    dla Tl > 3, /i = /₂ = 1.

Wykazać indukcyjnie tożsamości:

a)    fn+lfn-l ~ fl = (-1)",

b)    ,/l • f'2 ! h t---- \ fn ¹ fn+2 ~ 1,

c)    /2 + /4 + fe 4-----h f2n = jżn+l ~ 1-

Zad 6. Stosując metodę funkcji charakterystycznej wyznaczyć rozwiązania rekurencji:

&)    6tt_n_25 Uo — 2, Ui — 5,

b)    b_n = 3b_n—i 2u_n_2, 6o — 2, b\ = 3,

c)    c^ 4c_n_i 4:C_n—2j c₀ 2, ci 3,

d)    d_n — 2d_n_i -h 3d_n_2, do — 1, di = 3, c) c_n 2e_n_i e_n_2, Co 3, ei 0,

f) f_n = 2/_n_i + 5/_n_₂ - 6/_n_₃, /o = 9, /i = -18, /₂ = 66.