MatDys 2008 2

MatDys 2008 2, studia, matematyka dyskretna

[ Pobierz całość w formacie PDF ]
1
MatematykaDyskretna2/2008.
1.W ka»dym z nast¦puj¡cych przypadków podaj jawny wzór na s
n
i udowodnij indukcyjnie jego poprawno±¢:
(a) s
0
=3; s
1
=6, oraz s
n
=s
n1
+2s
n2
dla n>2;
(b) s
0
=1; s
1
=3, oraz s
n
=6s
n1
9s
n2
dla n>2;
(c) s
0
=c; s
1
=d, oraz s
n
=5s
n1
6s
n2
dla n>2;
(d) s
0
=1; s
1
=2, oraz s
n
=3s
n2
dla n>2.
2.W ka»dym z nast¦puj¡cych przypadków podaj jawny wzór na s
2
n
i udowodnij indukcyjnie jego poprawno±¢:
(a) s
1
=1, s
2n
=2s
n
+3; (b) s
1
=0, s
2n
=2s
n
+5n;
(c) s
1
=1, s
2n
=2s
n
7; (d) s
1
=0, s
2n
=2s
n
+57n.
3.Dla ka»dego z ci¡gów zdefiniowanych rekurencyjnie wyznaczy¢ trzeci, pi¡ty i dziesi¡ty wyraz oraz udo-
wodni¢ podan¡ nierówno±¢:
(a) a
0
=1; a
1
=2; a
2
=3oraz a
n
=a
n2
+2a
n3
dla n>3; a
n
>(
3
2
)
n
dla wszystkich n>1;
(b) a
0
=a
1
=a
2
=1oraz a
n
=a
n1
+a
n2
+a
n3
dla n>3; a
n
62
n1
dla wszystkich n>1;
(c) a
0
=1; a
1
=3; a
2
=5oraz a
n
=3a
n2
+2a
n3
dla n>3;2
n
< a
n
62
n+1
dla wszystkich n>1.
4.Niech F
0
=0, F
1
=1i dla n>2F
n
=F
n1
+F
n2
.
(a) Udowodni¢ »e F
n+1
F
n1
F
2
n
=(1)
n
, dla dowolnej liczby naturalnej n.
(b) Czy F
2
n
+F
2
n+1
jest zawsze liczb¡ Fibonacciego?
(c) Wyrazi¢
n
P
F
k
za pomoc¡ liczb Fibonacciego.
k=0
5.Niech a
0
=1, a
2
=8; a
3
=27, a
4
=64i dla d>0niech
a
n+4
=4a
n+3
6a
n+2
+4a
n+1
a
n
:
Odgadn¡¢ jawn¡ posta¢ n-tego wyrazu ci¡gu a
n
i udowodni¢ jego poprawno±¢.
6.Niech
P
=fa;b;cg i niech s
n
oznacza liczb¦ słów długo±ci n w alfabecie
P
, w których nie wyst¦puje ci¡g
aa. Obliczy¢ pi¡ty, sódmy i dziesi¡ty wyraz ci¡g s
n
i znale¹¢ dla niego wzór rekurencyjny.
7.Niech
P
=fa;bg.
(a) Niech s
n
oznacza liczb¦ słów długo±ci n w alfabecie
P
, nie zawieraj¡cych ci¡gu ab. Obliczy¢ pi¡ty
szósty i siódmy wyraz ci¡gu s
n
, znale¹¢ jawny wzór na s
n
i go udowodni¢.
(b) Niech t
n
oznacza liczb¦ słów długo±ci n w alfabecie
P
, w których jest parzysta liczba liter a. Obliczy¢
pi¡ty szósty i siódmy wyraz ci¡gu t
n
, znale¹¢ jawny wzór na t
n
i go udowodni¢.
a
n
2
dla n>2. Poda¢ jawny wzór na a
n
. Jakie
warunki musz¡ spełnia¢ i , je»eli ten ci¡g jest niesko«czony?
9.(a) Definiujemy rekurencyjnie s
0
=1i s
n+1
=
2
s
n
dla n>0. Obliczy¢ pi¡ty, dziesi¡ty i pi¦tnasty wyraz
tego ci¡gu. Jaki jest zbiór warto±ci ci¡gu fs
n
g?
(b) Definiujemy rekurencyjnie a
0
=0, a
1
=1, a
2
=2oraz a
n
=a
n1
a
n2
+a
n3
dla n>3. Jaki jest
zbiór warto±ci ci¡gu fa
n
g?
10.Obliczy¢ wyznacznik macierzy nn:
0
110 0 :::00 0
1 110 :::00 0
0 1 11:::00 0
0 0 0 0 :::111
0 0 0 0 :::01 1
1
@
A
:
8.Obliczy¢ a
4
;a
5
i a
6
je»eli a
0
=, a
1
= oraz a
n
=
1+a
n
1
2
11.Podaj definicj¦ rekurencyjn¡ ka»dego z poni»szych ci¡gów:
a)(1;3;9;27;81;:::); b)(2;2
2
;(2
2
)
2
;((2
2
)
2
)
2
;:::); c)(2;2
2
;2
(2
2
)
;2
(2
(2
2
)
)
).
12.a) Definiujemy rekurencyjnie ci¡g za pomoc¡ wzorów: a
0
=a
1
=1oraz a
n
=a
n1
+2a
n2
dla n>2.
Obliczy¢ a
6
i pokaza¢, »e wszystkie wyrazy ci¡gu s¡ nieparzyste.
b) Definiujemy rekurencyjnie ci¡g za pomoc¡ wzorów: b
0
=b
1
=1oraz b
n
=2b
n1
+b
n2
dla n>2.
Obliczy¢ b
6
i pokaza¢, »e wszystkie wyrazy ci¡gu s¡ nieparzyste.
[ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

mement.xlx.pl