LISTA ZADA NR
5
Z MATEMATYKI DYSKRETNEJ
Ci gi, równania ró nicowe, zasada indukcji matematycznej
1. Definiujemy rekurencyjnie ci g:
1
1
=
s
i
n
n
s
s
/
2
1
=
+
dla
+
∈ N
n
.
a) Wypisz kilka pierwszych wyrazów tego ci gu.
b) Je li jest zbiór warto ci ci gu s?
2. We my ci g c: 1, 3, 9, 27, 81,...
a) Podaj wzór ogólny na n-ty wyraz ci gu.
b) Okre l ten ci g rekurencyjnie.
3. Okre l rekurencyjnie nast puj ce ci gi:
a)
!
n
a
n
=
b)
=
=
+
+
+
+
+
=
n
i
n
i
n
b
1
...
4
3
2
1
.
c)
=
=
n
i
n
i
c
1
!
1
.
d)
∏
=
=
n
i
n
i
d
1
2
.
4. Podaj wzór ogólny na
n
s , dla ci gu okre lonego rekurencyjnie:
3
1
=
s
i
1
2
−
−
=
n
n
s
s
dla
2
≥
n
.
5. Sprawd , e ci g
n
n
n
s
)
1
(
2
1
−
+
=
+
spełnia warunki:
3
1
=
s
,
9
2
=
s
i
2
1
2
−
−
+
=
n
n
n
s
s
s
dla
3
≥
n
6. Wyka , e podane ni ej wyra enia s rozwi zaniami równania rekurencyjnego postaci
0
2
1
=
+
+
−
−
n
n
n
Bs
As
s
, gdzie A i B s stałymi liczbami:
a)
n
n
n
r
C
r
C
s
2
2
1
1
+
=
gdy równanie charakterystyczne:
0
2
=
+
+
B
Ax
x
ma dwa ró ne rozwi zania
1
r ,
2
r ;
b)
n
n
r
C
n
C
s
)
(
2
1
+
=
gdy równanie charakterystyczne ma jedno rozwi zanie r.
7. W ka dym z nast puj cych przypadków podaj wzór jawny na
n
s :
a)
1
1
−
=
s
,
13
2
=
s
i
2
1
6
−
−
+
−
=
n
n
n
s
s
s
dla
3
≥
n
.
b)
8
1
=
s
,
28
2
=
s
i
2
1
4
4
−
−
−
=
n
n
n
s
s
s
dla
3
≥
n
.
c)
4
1
=
s
,
1
2
=
s
i
2
−
=
n
n
s
s
dla
3
≥
n
.
d)
1
1
=
s
,
1
2
−
=
s
i
2
4
−
−
=
n
n
s
s
dla
3
≥
n
.
Warto ci stałych
1
C i
2
C wyznacz z warunków pocz tkowych.
8. Korzystaj c z twierdzenia o indukcji matematycznej udowodnij prawdziwo wzorów:
a)
1
4
)
1
4
)(
3
4
(
1
...
13
9
1
9
5
1
5
1
1
+
=
+
−
+
+
⋅
+
⋅
+
⋅
n
n
n
n
dla
+
∈ N
n
.
b)
)
1
2
)(
1
(
3
1
...
9
4
1
2
+
+
=
+
+
+
+
n
n
n
n
dla
+
∈ N
n
.
c) wzór na sum n pocz tkowych wyrazów ci gu geometrycznego:
q
q
a
S
n
n
−
−
=
1
1
1
, je li
1
≠
q
.
