´

Cwiczenia 10. Indukcja matematyczna.

Matematyka dyskretna

Anna Danielewska c

2004

Problem 1:
Jak udowodni´

c nast¸epuj¸

ace r´

ownanie?

1 + 3 + 5 + · · · + (2n − 1) = n

2

∀ n ∈ N.

Rozwi¸

azanie:

Poniewa˙z r´

ownanie ma by´

c spe lnione dla liczb naturalnych zacznijmy od

pierwszej z nich, a potem spr´

obujmy to pokaza´

c dla wszystkich pozosta lych.

R´

owno´s´

c jest oczywi´scie prawdziwa dla n = 1, bo 1 = 1

2

. Przypu´s´

cmy,

˙ze jest prawdziwa dla pewnej warto´sci n, n = k, a wi¸ec

1 + 3 + 5 + · · · + (2k − 1) = k

2

.

U˙zyjemy tego faktu aby upro´sci´

c lew¸

a stron¸e r´

owno´sci, gdy n = k + 1:

1 + 3 + 5 + · · · + (2k − 1) + (2k + 1) = k

2

+ (2k + 1)

= (k + 1)

2

.

A wi¸ec je´sli r´

ownanie jest prawdziwe dla n = k, to jest prawdziwe dla n =

k + 1. A zacz¸eli´smy od pokazania, ˙ze jest prawdziwe dla 1, b¸edzie wi¸ec
prawdziwe dla 1 + 1 = 2. Analogicznie b¸edzie prawdziwe dla 3. Kontynuuj¸

ac

to rozumowanie dojdziemy do wniosku, ˙ze jest prawdziwe dla ka˙zdego n
naturalnego.

1

Rdze´

n tego rozumowania nazywamy

zasad¸

a indukcji

i formuujemy go for-

malnie w nast¸epuj¸

acy spos´

ob:

Twierdzenie 1. Zasada indukcji zupe lnej
Je´sli W jest pewn¸

a w lasno´sci¸

a okre´slon¸

a w zbiorze liczb naturalnych N,

tak¸

a ˙ze

I. W (1)

(1 ma w lasno´s´

c W ),

II. dla ka˙zdej liczby naturalnej n : je´sli W (n) to W (n + 1),

(je´sli n ma w lasno´s´

c W , to n + 1 ma w lasno´s´

c W ),

to ka˙zda liczba naturalna ma w lasno´s´

c W .

Jest kilka modyfikacji zasady indukcji. Czasem wygodnie jest przyj¸

a´

c

za

baz¸e indukcji

(czyli pierwsz¸

a cz¸e´s´

c dowodu) n = 0, a czasem n = 3 lub

n = 4 bo pierwsze przypadki mog¸

a by´

c wyj¸

atkami. Ka˙zdy problem nale˙zy

traktowa´

c oddzielnie.

Przyk lad 1. Jak¸

a baz¸e indukcji nale˙zy przyj¸

a´

c dowodz¸

ac, ˙ze n! > 2

n

?

Rozwi¸

azanie:

Dla

n = 1

mamy

1 6> 2,

dla

n = 2

mamy

2 6> 4,

dla

n = 3

mamy

6 6> 8,

dla

n = 4

mamy

24 > 16.

Rozumowanie indukcyjne nale˙zy wi¸ec zacz¸

a´

c od n = 4.

Inn¸

a modyfikacj¸

a zasady indukcji jest

Twierdzenie 2. Silna zasada indukcji.

I. Je´sli pewne stwierdzenie jest prawdziwe dla pewnego ma lego n

0

∈ N,

oraz

II. je´sli jest prawdziwe dla wszystkich n < k, (k ∈ N), to jest prawdziwe

dla n = k,

to stwierdzenie jest prawdziwe dla ka˙zdej liczby naturalnej n ≥ n

0

.

2

Przyk lad 2. Udowodnij indukcyjnie

Twierdzenie.

1 · 2 + 2 · 3 + · · · + (n − 1)n =

(n − 1)n(n + 1)

3

,

dla n ≥ 1

Dow´

od indukcyjny:

I. dla n = 1 mamy 0 · 1 =

0·1·2

3

= 0

II. za l´

o˙zmy, ˙ze

1 · 2 + 2 · 3 + · · · + (n − 1)n =

(n − 1)n(n + 1)

3

,

poka˙zemy, ˙ze wtedy

1 · 2 + 2 · 3 + · · · + (n − 1)n + n(n + 1) =

n(n + 1)(n + 2)

3

.

Przekszta lcamy lew¸

a stron¸e tezy

1 · 2 + 2 · 3 + · · · + (n − 1)n
|

{z

}

=

(n−1)n(n+1)

3

z za lo ˙zenia

+n(n + 1)

=

(n − 1)n(n + 1)

3

+ n(n + 1) =

(n − 1)n(n + 1) + 3n(n + 1)

3

=

(n + 1)((n − 1)n + 3n))

3

=

(n + 1)(n

2

− n + 3n)

3

=

(n + 1)(n

2

+ 2n)

3

=

n(n + 1)(n + 2)

3

.

3

Przyk lad 3. Definiujemy rekurencyjnie ci¸

ag x

n

w nast¸epuj¸

acy spos´

ob

x

1

= 2,

x

n

= x

n−1

+ 2n

(n ≥ 2),

udowodnij indukcyjnie, ˙ze prawdziwy jest wz´

or na kolejne wyrazy ci¸

agu:

x

n

= n(n + 1)

∀n ∈ N.

Dow´

od indukcyjny:

I. dla n = 1 mamy x

1

= 2 = 1 · 2

II. za l´

o˙zmy, ˙ze wz´

or jest prawdziwy dla n ≥ 2

x

n

= n(n + 1)

poka˙zemy, ˙ze wtedy jest te˙z prawdziwy dla n + 1:

x

n+1

= (n + 1)(n + 2).

Ze wzoru rekurencyjnego na kolejne wyrazy ci¸

agu, mamy

x

n+1

= x

n

+ 2n

=

|{z}

z zal. ind.

n(n + 1) + 2(n + 1) = (n + 2)(n + 1).

4

Przyk lad 4. Udowodnij indukcyjnie

Twierdzenie.

3|n

3

− n

∀ n ∈ N

Dow´

od indukcyjny:

I. dla n = 1 mamy 3|1 − 1 = 0, co jest prawd¸

a bo ka˙zda

liczba dzieli zero (na zero cz¸e´sci).

II. za l´

o˙zmy, ˙ze

3|n

3

− n,

poka˙zemy, ˙ze wtedy

3|(n + 1)

3

− (n + 1).

Mamy

(n + 1)

3

− (n + 1) = n

3

+ 3n

2

+ 3n + 1 − n − 1 = n

3

+ 3n

2

+ 2n

Teraz musimy tak przekszta lci´

c tez¸e aby m´

oc skorzysta´

c z za lo˙zenia

indukcyjnego. Mamy wi¸ec

3|n

3

+3n

2

+2n ⇔ 3|n

3

−n+3n+3n

2

⇔ 3|

n

3

− n

|

{z

}

podzielne przez 3 z zal. ind.

+

3(n + n

2

)

|

{z

}

podzielne przez 3

Wi¸ec rzeczywi´scie (z prawa rozdzielno´sci mno˙zenia wzg. dodawania)

3|(n + 1)

3

− (n + 1).

Zadanie 1. Udowodnij indukcyjnie (1 + a)

n

≥ 1 + na, a > −1.

Zadanie 2. Udowodnij indukcyjnie

5|n

5

− n

∀ n ∈ N

Zadanie 3. Dla pewnych wyraz´

ow ci¸

agu Fibonacciego

a

1

= 1, a

2

= 1, a

n+1

= a

n

+ a

n−1

mamy

2|a

3n

i

3|a

4n

. Udowodnij te twierdzenia indukcyjnie.

5