Matematyka Dyskretna – Elektronika

2 marca 2009

Lista 2. Indukcja i rekurencja.

1. Niech F

n

oznacza ciąg Fibonacciego. Wykaż, że

a) F

1

+ F

2

+ . . . + F

n

= F

n+2

− 1;

b) F

1

+ F

3

+ F

5

+ . . . + F

2n−1

= F

2n

;

c) F

2

1

+ F

2

2

+ . . . + F

2

n

= F

n

F

n+1

.

2. Z szachownicy o wymiarach 2

n

× 2

n

usunięto jedno narożne pole. Wykaż, że otrzy-

maną figurę można pokryć tryminami, tzn. kostkami złożonymi z trzech kwadratów, w
kształcie równoramiennej elki.

3. Wiadomo, że dla pewnej własności W prawdziwa jest implikacja W (n) =⇒ W (n + 3)

dla n ≥ 7. Ponadto wiemy, że spełnione sa W (1) i W (11), ale nieprawdą jest W (31).
Co można powiedzieć o W (4), W (7), W (20), W (22), W (33), W (110).

4. Znajdź rozwiązanie ogólne dla każdego z poniższych równań:

a) a

n+2

= 2a

n+1

+ 3a

n

;

b) b

n+2

= 6b

n+1

− 9b

n

;

c) c

n+3

= −2c

n+2

+ c

n+1

+ 2c

n

;

d) e

n+2

= 2e

n+1

− 4e

n

.

5. Znajdź rozwiązanie szczególne dla każdego z poniższych równań:

a) a

1

= 2, a

2

= 3, a

n+2

= 6a

n+1

−5a

n

; b) b

1

= 3, b

2

= 1, b

n+2

= 4b

n+1

− 3b

n

;

c) c

1

= 7, c

2

= 10; c

n+2

= 2c

n+1

−4c

n

; d) d

1

= 2, d

2

= 3, d

3

= 5, d

n+3

= 7d

n+1

− 6d

n

.

6*. Stosując odpowiednie podstawienie, sprowadź poniższe równania do postaci liniowej, a

następnie znajdź ich rozwiązania szczególne:

a) a

1

= 2, a

2

n+1

= 4a

n

;

b) b

1

= 1, (n + 1)b

n+1

= b

n

+ 1.

7. Liczby Lucasa opisane są równaniem rekurencyjnym L

n+2

= L

n+1

+L

n

, L

0

= 2, L

1

= 1.

Znajdź wzór na L

n

.

8. Na ile sposobów można pokonać drogę złożoną z n schodków, gdy za każdym razem

przeskakujemy jeden stopień lub dwa.

9. Na ile sposobów można zbudować:

a) prostokąt 2 × n za pomocą kwadratów 1 × 1 oraz 2 × 2;
b) wieżę o wymiarach 2 × 2 × n z klocków o wymiarach 2 × 2 × 1?

10. Ile jest ciągów długości n o wyrazach A, C, G, T takich, że A nie sąsiaduje z A? Zapisz

zależność rekurencyjną.

11. Dla poniższego wyznacznika znajdź zależność rekurencyjną i oblicz jego wartość:

D

n

=



















2

1

0

0

. . .

0

0

0

1

2

1

0

. . .

0

0

0

0

1

2

1

. . .

0

0

0

0

0

1

2

. . .

0

0

0

..

.

..

.

..

.

..

.

. .. ... ... ...

0

0

0

0

. . .

2

1

0

0

0

0

0

. . .

1

2

1

0

0

0

0

. . .

0

1

2



















12*. Rozwiązując na dwa sposoby jedno z powyższych zadań wykaż, że zachodzi tożsamość

F

n+1

=

 n

0



+

 n − 1

1



+

 n − 2

2



+ . . . .

1/1