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
!
+ ...
