”Wst¸ep do Teorii Mnogości”, rok akademicki 2009/2010

9. Indukcja matematyczna i rekursja Zadanie 9.1 Udowodnić, że dla każdej liczby naturalnej n zachodzi (a) n < 2n;

n

X

1

13

(b)

>

;

n + i

24

i=1

n

X

(c)

(4i − 3) = n(2n − 1);

i=1

(d) 6 | n3 + 5n;

(e) 6 | 13n − 7;

n

X

(f)

2 · 3i−1 = 3n − 1;

i=1

n

X

(g)

(2i − 1) = n2 (Francesco Maurlico1, 1575r.).

i=1

Zadanie 9.2 Niech ci¸ag {an}n∈N b¸edzie określony wzorem 1

1

1

a0 = 0,

an = 1 +

+

+ . . . +

.

2

3

n

Udowodnić, że

n

X

(a)

ai = (n + 1)(an+1 − 1);

i=1

n

1 −1

X

(b) an = 1 +

ai.

n i=0

Zadanie 9.3 Udowodnić nierówność Bernoulliego2 (1689r.): dla każdego n ∈ N i x > −1

zachodzi 1 + nx ≤ (1 + x)n.

Zadanie 9.4 Niech ci¸ag liczbowy3 {an}n∈N b¸edzie określony rekurencyjnie wzorami: a0 = 0,

a1 = 1,

an+2 = an+1 + an.

Udowodnić, że dla każdego n ∈ N zachodzi

"

√ !n

√ !n#

1

1 +

5

1 − 5

(a) an = √

−

(wzór Bineta4, 1841r.);

5

2

2

(b) an+2an − a2

= (

n+1

−1)n+1 (wzór Cassiniego5, 1680r.).

Zadanie 9.5 Udowodnić, że dla każdej liczby naturalnej n ilość wszystkich podzbiorów zbioru n-elementowego jest równa 2n.

1 Francesco Maurlico (1494-1575) 2 Jacob Bernoulli (1654-1705) 3 Ci¸ag ten nazywamy ci¸agiem liczb Fibonacciego. Fibonacci (skrót od filius Bonacci) znany także jako Leonardo da Pisa opisa l go w ksi¸ażce Liber Abaci (ok. 1170r.) 4 Jacques Philippe Binet (1786-1856) 5 Giovanni Domenico Cassini (1625-1712)