MD_lista2.pdf

MatematykaDyskretna–Elektronika 2marca2009

Lista2.Indukcjairekurencja.

1.NiechF n oznaczaci¡gFibonacciego.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 .

2.Zszachownicyowymiarach2 n ×2 n usuni¦tojednonaro»nepole.Wyka»,»eotrzy-

man¡ﬁgur¦mo»napokry¢tryminami,tzn.kostkamizło»onymiztrzechkwadratów,w

kształcierównoramiennejelki.

3.Wiadomo,»edlapewnejwłasno±ciWprawdziwajestimplikacjaW(n)=)W(n+3)

dlan7.Ponadtowiemy,»espełnionesaW(1)iW(11),alenieprawd¡jestW(31).

Como»napowiedzie¢oW(4),W(7),W(20),W(22),W(33),W(110).

4.Znajd¹rozwi¡zanieogólnedlaka»degozponi»szychró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¡zanieszczególnedlaka»degozponi»szychró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¡codpowiedniepodstawienie,sprowad¹poni»szerównaniadopostaciliniowej,a

nast¦pnieznajd¹ichrozwi¡zaniaszczególne:

a)a 1 =2,a 2 n +1 =4a n ; b)b 1 =1,(n+1)b n +1 =b n +1.

7.LiczbyLucasaopisanes¡równaniemrekurencyjnymL n +2 =L n +1 +L n ,L 0 =2,L 1 =1.

Znajd¹wzórnaL n .

8.Nailesposobówmo»napokona¢drog¦zło»on¡znschodków,gdyzaka»dymrazem

przeskakujemyjedenstopie«lubdwa.

9.Nailesposobówmo»nazbudowa¢:

a)prostok¡t2×nzapomoc¡kwadratów1×1oraz2×2;

b)wie»¦owymiarach2×2×nzklockówowymiarach2×2×1?

10.Ilejestci¡gówdługo±cinowyrazachA,C,G,Ttakich,»eAnies¡siadujezA?Zapisz

zale»no±¢rekurencyjn¡.

11.Dlaponi»szegowyznacznikaznajd¹zale»no±¢rekurencyjn¡iobliczjegowarto±¢:

D n =

2100...000

1210...000

0121...000

0012...000

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

0000...210

0000...121

0000...012

12*.Rozwi¡zuj¡cnadwasposobyjednozpowy»szychzada«wyka»,»ezachodzito»samo±¢

F n +1 =

n−1

n−2

+....

1/1