1

MATEMATYKA DYSKRETNA - Elektronika

Lista 5 - Indukcja i rekurencja

1. Wykaż za pomocą indukcji matematycznej prawdziwość wzorów

a) 1 + 3 + 5 + ... + (2n − 1) = n

2

;

b) 1 · 2 + 2 · 3 + ... + n(n + 1) =

n(n + 1)(n + 2)

3

.

Uzasadnij wzór a) bez pomocy indukcji za pomocą rozumowania geometrycznego.

2. Odgadnij wzór na sumę i wykaż jego prawdziwość za pomocą indukcji matematycz-
nej:

a) 1 +

1

√

1 +

√

2

+

1

√

2 +

√

3

+ ... +

1

√

n − 1 +

√

n

.

b) 1 +

1

1 · 3

+

1

3 · 5

+ ... +

1

(2n − 1)(2n + 1)

.

4. Liczby Fibonacciego określone sa wzorami F

1

= F

2

= 1 oraz F

n+2

= F

n

+ F

n+1

.

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

.

5. Jacek wykazał, że dla pewnej własności W dla n ­ 7 zachodzi W (n) −→ W (n + 3).
Sprawdził też, że zachodzi W (1), W (11) ale nieprawda, że W (31). Wyjaśnij, o ile jest
to możliwe, czy własność W zachodzi dla: a) 20; b) 110, c) 22; d) 7; e) 33; f)4.

6. Z szachownicy o wymiarach 2

n

× 2

n

usunięto jedno pole. Wykaż, że otrzymaną figurę

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

7. 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) d

n+3

= d

n+2

− d

n+1

+ d

n

;

e) e

n+2

= 2e

n+1

− 4e

n

;

f) f

n+2

= −2f

n+1

− 2f

n

.

8. Znajdź rozwiązanie szczególne:

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

9. Liczby Lucasa opisane są rekurencją L

n+2

= L

n+1

+ L

n

, L

0

= 2, L

1

= 1. Znajdź

wzór na L

n

.

10. 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?

11. 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?

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

!

+

n − 3

3

!

+ ...

2

13*.Dla poniższego wyznacznika znajdź zależność rekurencyjną i oblicz jego wartość,
rozwiązując odpowiednie równanie rekurencyjne.

D

n

=


















2

1

0

0

0 ... 0

0

0

1

2

1

0

0 ... 0

0

0

0

1

2

1

0 ... 0

0

0

0

0

1

2

1 ... 0

0

0

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

0

0

0

0

0 ... 1

2

1

0

0

0

0

0 ... 0

1

2