5638685083

imię i nazwisko:

MATEMATYKA DYSKRETNA 2

numer indeksu:

1³ +2³+3^J+...+„’₌

(a) 3,

PodSln?^ef^{UkC)l matematyczne}i    Pokazać, że F(4n), gdzie F(n) oznacza n-ty wyraz ciągu Fibonacdego jest

0)2,    (c)4

3    Rozważmy algorytm Alg(n), neZ.

Alg(m)={z:=2; k:=1;

while (k <= m) do k:=k+1; z:=z*k; od;}

Która z poniższych formut jest niezmiennikiem pętli w tym algorytmie’

(a) z =2*kl,    (b) k=zl,    (_C) k<z.

4    Stosując zasadę indukcji matematycznej można udowodnić, że dla każdej liczby naturalnej n, n>-n jest podzielne przez

(a) 5.    (b) 4,    (c) 3.

5.    Ciąg s(n) = 3" - 2 n-3" jest rozwiązaniem równania

(a)    s(0)=s(1)=1; s(n)=6s(n-1)-9s(n-2) dla n>1,

(b)    s(0)=1, s(1)=-3; s(n)=6s(n-1)-s(n-2) dla n>1,

(c)    s(0)=1, s(1)=-3; s(n)=6s<n-1)-9s(n-2) dla n>1.

6.    Rozwiązaniem równania rekurencyjnego ao = 3, ai= -1, &.2 = -a„.i + 20a* jest ciąg

(a) an = 14/9*4ⁿ + 13/9*(-5)",    (b) a*= 14/9*4"+ 5".    (c) a„= 14*4”+ 13*(-5)».

7.    Oszacuj rząd rozwiązania równania rekurencyjnego T(n)=3T(rV3)+3n-5 (a) T(n)=n, (b) T(n)=lg(n). (c) T(n)=nlg(n).

8.    Mamy dwa rodzaje prętów: o długości 1 i o długości 2. Wzór rekurencyjny określający liczbę sposobów zbudowania z tych prętów masztu o wysokości n to

(a) a(n)=2a(n-1)+a(n-2), (b) a(n)=a(n-1)+a(n-2), (c) a(n)=2a(n-1)-2a(n-2).

9.    Zasada Szufladkowa Dirichleta pozwala udowodnić, że wśród dowolnie wybranych jedenastu liczb czterocyfrowych zawsze znajdą się

(a) dwie,    (b)trzy. ^

dla których piąte potęgi cyfr setek są równe.

,0 O nw> *«*>•"»• że na i*>    *>““ * •«*> e™”""”** ">^{,le s}‘^ra0‘*'

(a) 6".