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

.

d) wzór na sum n pocz tkowych wyrazów ci gu arytmetycznego:

n

a

a

S

n

n

2

1

+

=

.

e)

n

n

n

n

n

b

a

n

n

b

a

n

b

a

n

b

a

n

b

a

0

2

2

1

1

0

...

2

1

0

)

(

+

+

+

+

=

+

−

−

dla dowolnych

R

∈

b

a,

i

+

∈ N

n

- wzór dwumianowy Newtona.
f) liczba

2

4

n

n

−

jest podzielna przez 3 dla wszystkich

N

∈

n

.

g) liczba

n

n

)

1

(

10

−

−

jest podzielna przez 11 dla wszystkich

N

∈

n

.

h)

nx

x

n

+

≥

+

1

)

1

(

dla dowolnych

R

∈

x

,

1

−

≥

x

i

+

∈ N

n

- nierówno Bernoulliego.

i)

n

n

1

2

1

...

3

1

2

1

1

2

2

2

−

≤

+

+

+

+

dla

+

∈ N

n

.

j)

1

1

1

+

≤

+

≤

n

n

n

n

n

dla

+

∈ N

n

. Wskazówka: skorzysta z nierówno ci Bernoulliego.

Dorota Majorkowska-Mech