dyskretna_lista5.pdf

MATEMATYKA DYSKRETNA - Elektronika

Lista5-Indukcjairekurencja

1. Wyka» za pomoc¡ indukcji matematycznej prawdziwo±¢ wzorów

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

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

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:

p n − 1 + p n .

a) 1 +

2 +

3 + ... +

1 +

b) 1 +

1 · 3 +

3 · 5 + ... +

(2 n − 1)(2 n + 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 2 n − 1 = F 2 n .

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¡ ﬁgur¦

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 = 2 a n +1 + 3 a n b) b n +2 = 6 b n +1 − 9 b n

c) c n +3 = − 2 c n +2 + c n +1 + 2 c n ;

d) d n +3 = d n +2 − d n +1 + d n ;

8. Znajd¹ rozwi¡zanie szczególne:

a) a 1 = 2, a 2 = 3, a n +2 = 6 a n +1 − 5 a n b) b 1 = 3, b 2 = 1, b n +2 = 4 b n +1 − 3 b 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±¢

n − 1

n − 2

n − 3

F n +1 =

+ ...

e) e n +2 = 2 e n +1 − 4 e n ;

f) f n +2 = − 2 f n +1 − 2 f n .

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

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: