Ćwiczenia 10. Indukcja matematyczna.
Matematyka dyskretna
Anna Danielewska © 2004
Problem 1:
Jak udowodnić nast¸ ace równanie?
epuj¸
1 + 3 + 5 + · · · + (2n - 1) = n2 " n " N.
Rozwi¸
azanie:
Ponieważ równanie ma być spe dla liczb naturalnych zacznijmy od
lnione
pierwszej z nich, a potem spróbujmy to pokazać dla wszystkich pozosta
lych.
Równość jest oczywiście prawdziwa dla n = 1, bo 1 = 12. Przypuśćmy,
że jest prawdziwa dla pewnej wartoÅ›ci n, n = k, a wi¸
ec
1 + 3 + 5 + · · · + (2k - 1) = k2.
Użyjemy tego faktu aby uproÅ›cić lew¸ stron¸ równoÅ›ci, gdy n = k + 1:
a e
1 + 3 + 5 + · · · + (2k - 1) + (2k + 1) = k2 + (2k + 1)
= (k + 1)2.
A wi¸ jeÅ›li równanie jest prawdziwe dla n = k, to jest prawdziwe dla n =
ec
k + 1. A zacz¸ od pokazania, że jest prawdziwe dla 1, b¸ wi¸
eliśmy edzie ec
prawdziwe dla 1 + 1 = 2. Analogicznie b¸ prawdziwe dla 3. Kontynuujac
edzie ¸
to rozumowanie dojdziemy do wniosku, że jest prawdziwe dla każdego n
naturalnego.
1
RdzeÅ„ tego rozumowania nazywamy zasad¸ indukcji i formuujemy go for-
a
malnie w nast¸ ¸ sposób:
epujacy
Twierdzenie 1. Zasada indukcji zupe
lnej
JeÅ›li W jest pewn¸ w ¸ a
a lasnoÅ›cia okreÅ›lon¸ w zbiorze liczb naturalnych N,
tak¸ że
a
I. W (1) (1 ma w
lasność W ),
II. dla każdej liczby naturalnej n : jeśli W (n) to W (n + 1),
(jeśli n ma w lasność W ),
lasność W , to n + 1 ma w
to każda liczba naturalna ma w
lasność W .
Jest kilka modyfikacji zasady indukcji. Czasem wygodnie jest przyjać
¸
za baz¸ indukcji (czyli pierwsz¸ cz¸Å›Ä‡ dowodu) n = 0, a czasem n = 3 lub
e a e
n = 4 bo pierwsze przypadki mog¸ być wyjatkami. Każdy problem należy
a ¸
traktować oddzielnie.
Przyk 1. Jak¸ baz¸ indukcji należy przyjać dowodz¸ że n! > 2n?
lad a e ¸ ac,
Rozwi¸
azanie:
Dla n = 1 mamy 1 > 2,

dla n = 2 mamy 2 > 4,

dla n = 3 mamy 6 > 8,

dla n = 4 mamy 24 > 16.
Rozumowanie indukcyjne należy wi¸ zacz¸Ä‡ od n = 4.
ec a
Inn¸ modyfikacj¸ zasady indukcji jest
a a
Twierdzenie 2. Silna zasada indukcji.
I. Jeśli pewne stwierdzenie jest prawdziwe dla pewnego ma n0 " N,
lego
oraz
II. jeśli jest prawdziwe dla wszystkich n < k, (k " N), to jest prawdziwe
dla n = k,
to stwierdzenie jest prawdziwe dla każdej liczby naturalnej n e" n0.
2
Przyk 2. Udowodnij indukcyjnie
lad
Twierdzenie.
(n - 1)n(n + 1)
1 · 2 + 2 · 3 + · · · + (n - 1)n = , dla n e" 1
3
0·1·2
Dowód indukcyjny: I. dla n = 1 mamy 0 · 1 = = 0
3
II. za óżmy, że
l
(n - 1)n(n + 1)
1 · 2 + 2 · 3 + · · · + (n - 1)n = ,
3
pokażemy, że wtedy
n(n + 1)(n + 2)
1 · 2 + 2 · 3 + · · · + (n - 1)n + n(n + 1) = .
3
Przekszta lew¸ stron¸ tezy
lcamy a e
1 · 2 + 2 · 3 + · · · + (n - 1)n +n(n + 1)

(n-1)n(n+1)
= z za
lożenia
3
(n - 1)n(n + 1) (n - 1)n(n + 1) + 3n(n + 1)
= + n(n + 1) =
3 3
(n + 1)((n - 1)n + 3n)) (n + 1)(n2 - n + 3n)
= =
3 3
(n + 1)(n2 + 2n) n(n + 1)(n + 2)
= = .
3 3
3
Przyk 3. Definiujemy rekurencyjnie ciag xn w nast¸ acy sposób
lad ¸ epuj¸
x1 = 2, xn = xn-1 + 2n (n e" 2),
udowodnij indukcyjnie, że prawdziwy jest wzór na kolejne wyrazy ciagu:
¸
xn = n(n + 1) "n " N.
Dowód indukcyjny: I. dla n = 1 mamy x1 = 2 = 1 · 2
II. za óżmy, że wzór jest prawdziwy dla n e" 2
l
xn = n(n + 1)
pokażemy, że wtedy jest też prawdziwy dla n + 1:
xn+1 = (n + 1)(n + 2).
Ze wzoru rekurencyjnego na kolejne wyrazy ciagu, mamy
¸
xn+1 = xn + 2n = n(n + 1) + 2(n + 1) = (n + 2)(n + 1).

z zal. ind.
4
Przyk 4. Udowodnij indukcyjnie
lad
Twierdzenie.
3|n3 - n " n " N
Dowód indukcyjny: I. dla n = 1 mamy 3|1-1 = 0, co jest prawd¸ bo każda
a
liczba dzieli zero (na zero cz¸Å›ci).
e
II. za óżmy, że
l
3|n3 - n,
pokażemy, że wtedy
3|(n + 1)3 - (n + 1).
Mamy
(n + 1)3 - (n + 1) = n3 + 3n2 + 3n + 1 - n - 1 = n3 + 3n2 + 2n
Teraz musimy tak przekszta tez¸ aby móc skorzystać z za
lcić e lożenia
indukcyjnego. Mamy wi¸
ec
3|n3+3n2+2n Ô! 3|n3-n+3n+3n2 Ô! 3| n3 - n + 3(n + n2)


podzielne przez 3 z zal. ind.
podzielne przez 3
Wi¸ rzeczywiÅ›cie (z prawa rozdzielnoÅ›ci mnożenia wzg. dodawania)
ec
3|(n + 1)3 - (n + 1).
Zadanie 1. Udowodnij indukcyjnie (1 + a)n e" 1 + na, a > -1.
Zadanie 2. Udowodnij indukcyjnie
5|n5 - n " n " N
Zadanie 3. Dla pewnych wyrazów ciagu Fibonacciego
¸
a1 = 1, a2 = 1, an+1 = an + an-1 mamy
2|a3n i 3|a4n. Udowodnij te twierdzenia indukcyjnie.
5