Matemaatiline sissejuhatus: materjal, näidisülesanded, tõestused

Matemaatiline induktsioon on deduktiivse tõestuse meetod, mida kasutatakse hästi järjestatud numbrikomplektiga seotud matemaatiliste väidete tõestamiseks.

Need numbrid on näiteks looduslikud arvud ja looduslike arvude tühjad alamhulgad.

Peate märkima: et matemaatilist induktsiooni kasutatakse ainult väite või valemi tõesuse kontrollimiseks või tõestamiseks. Ja matemaatiline induktsioon ei ole valemite tuletamine.

Matemaatilist induktsiooni ei saa kasutada valemite tuletamiseks ega leidmiseks.

Järgnevalt on toodud mõned matemaatiliste väidete näited, mida saab tõendada matemaatilise induktsiooni abil:

P (n): 2 + 4 + 6 +… + 2n = n (n + 1), n ​​loomulikku arvu
P (n): 6ⁿ + 4 jagub 5-ga, n loodusarvu korral.
P (n): 4n <2ⁿ, iga loodusliku arvu n 4 korral

Kõige lihtsam on matemaatilise induktsiooni printsiibi väljaselgitamiseks jälgida doominoefekti.

Alustuseks võime esitada küsimuse: "millal kõik doominod kukuvad".

Kõigi ülaltoodud doomino langemiseks peavad olema täidetud kaks tingimust.

Esiteks: doomino 1 peab langema.

Teiseks: on tõsi, et iga langeva doomino puhul langeb järgmisena täpselt üks doomino.

See tähendab, et domino 1 kukkumisel peab domino 2 kukkuma, doomino 2 kukkudes peab domino 3 langema ja nii edasi.

Üldiselt võime öelda, millal domino k langeb, siis langeb ka domino (k + 1) ja see järeldus kehtib kõigi doomino kohta.

Kui kaks ülaltoodud tingimust on täidetud, on kindel, et kõik doomino langevad.

Matemaatilise induktsiooni põhimõte

Näiteks P (n) on lause, mis sõltub n-st. P (n) on tõene iga naturaalse arvu kohta, kui see vastab kahele järgmisele tingimusele:

1. P (1) on tõene, mis tähendab, et kui n = 1, siis P (n) on tõene.
2. Kui P (k) on tõene, on iga naturaalarvu k korral ka P (k + 1).

1. P (m) on tõene, mis tähendab, et kui n = m, siis P (n) on tõene
2. Kui P (k) on tõene, on iga naturaalarvu k m korral ka P (k + 1).

P (1) tõesuse näitamiseks piisab, kui asendada P (n) -ga n = 1.

Kui P (n) esitatakse võrrandi kujul, tähendab see, et vasak pool peab võrduma parempoolse küljega n = 1, ja siis järeldame, et P (1) on tõene.

Saame rakendada sama meetodit, et näidata P (m) on tõene.

Tagasi ülaltoodud doomino juhtumi juurde, et domino (k + 1) langeda, on esimene asi, et k domeen peab langema.

Ja sellele järgneb implikatsioon "kui domino k langeb, siis domino (k + 1) langeb" võib juhtuda.

Nii et implikatsiooni "kui P (k) on tõene, siis P (k + 1) on tõene" näitamiseks peab meie esimene samm olema eeldus, et P (k) on tõene.

Neid eeldusi vaadates näitame, et ka P (k + 1) on tõene.

Seda protsessi P (k) tõesuse eeldamiseks nimetatakse induktsiooni hüpotees.

P (k + 1) näitamiseks on tõsi, siis võime alustada hüpotees. See tähendab eeldusest, et P (k) on tõene või sellest järeldussee tähendab P-st (k + 1) endast.

Matemaatilise induktsiooni tõendamise etapid

Ülaltoodud selgituse põhjal saab matemaatilise induktsiooni tõestamise samme teha järgmises järjekorras:

1. Esialgne samm: Näitab, et P (1) vastab tõele.
2. Sissejuhatus: Oletame, et P (k) on tõene kõigi k loodusarvude puhul, siis näitab nende eelduste põhjal ka P (k + 1).
3. Järeldus: P (n) kehtib iga naturaalse arvu n kohta.

Seeria tõestus

Enne tõestavate seeriate alustamist tuleb sarjade osas hoolikalt läbi mõelda mitu asja. Teiste hulgas:

Kui

P (n): u₁ + u₂ + u₃ +… + U_n = S_nsiis
P (1): u₁ = S₁
P (k): u₁ + u₂ + u₃ +… + U_k = S_k
P (k + 1): u₁ + u₂ + u₃ +… + U_k + u_{k + 1} = S_{k + 1}

Näiteks 1:

Tõestage 2 + 4 + 6 +… + 2n = n (n + 1) iga naturaalse arvu kohta.

Vastus:
P (n): 2 + 4 + 6 +… + 2n = n (n + 1)

Tõestame, et P (n) on tõene iga n N kohta

Esialgne samm:

P (1) näitamine vastab tõele
2 = 1(1 + 1)

Nii et saame, on P (1) tõene

Sissejuhatus:

Oletame, et P (k) on tõene, nimelt:
2 + 4 + 6 +… + 2k = k (k + 1), k N

P (k + 1) näitab ka, et:
2 + 4 + 6 +… + 2k + 2 (k + 1) = (k + 1) (k + 1 + 1)

Ülaltoodud eelduste põhjal:
2 + 4 + 6 +… + 2k = k (k + 1)

Lisage mõlemad pooled u-ga_{k + 1} :
2 + 4 + 6 +… + 2k + 2 (k + 1) = k (k + 1) + 2 (k + 1)
2 + 4 + 6 +… + 2k + 2 (k + 1) = (k + 1) (k + 2)
2 + 4 + 6 +… + 2k + 2 (k + 1) = (k + 1) (k + 1 + 1)

Niisiis, P (k + 1) on tõene

Matemaatilise induktsiooni põhimõttele tuginedes on tõestatud, et P (n) on tõene kõigi n loodusarvu kohta.

Näiteks 2:

Tõesta seda 1 + 3 + 5 +… + (2n 1) = n² see on tõsi, iga naturaalse arvu korral.

Vastus:
P (n): 1 + 3 + 5 +… + (2n1) = n²

Siis näitab see, et P (n) on tõene iga n N2 kohta

Esialgne samm:
Näitab, et P (1) on tõene
1 = 1²

Niisiis, P (1) vastab tõele

Sissejuhatus:
Oletame, et P (k) on tõene, nimelt:
1 + 3 + 5 +… + (2k1) = k², k N

See näitab, et ka P (k + 1) on tõene, st:
1 + 3 + 5 +… + (2k 1) + (2 (k + 1) 1) = (k + 1)²

Ülaltoodud eelduste põhjal:
1 + 3 + 5 +… + (2k1) = k²

Lisage mõlemad pooled u-ga_{k + 1} :
1 + 3 + 5 +… + (2k1) + (2 (k + 1) 1) = k² + (2 (k + 1) 1)
1 + 3 + 5 +… + (2k1) + (2 (k + 1) 1) = k² + 2k + 1
1 + 3 + 5 +… + (2k 1) + (2 (k + 1) 1) = (k + 1)²

Niisiis, P (k + 1) on ka tõsi

Matemaatilise induktsiooni põhimõttele tuginedes on tõestatud, et P (n) on tõene kõigi n loodusarvu kohta.

Jaotustõend

Väide "a jagub b-ga", mis on sünonüüm järgmisega:

• b kordne
• b tegur a
• b jagab a

Kui p jagub a-ga ja q jagub a-ga, siis (p + q) jagub ka.

Näiteks 4 jagub 2-ga ja 6 jagub 2-ga, seega (4 + 6) jagub ka 2-ga

Näide 3:

Tõestage 6ⁿ + 4 jagub 5-ga iga n loodusarvu korral.

Vastus:

P (n): 6ⁿ + 4 jagub 5-ga

Tõestame, et P (n) on tõene iga n N kohta.

Esialgne samm:

Näitab, et P (1) on tõene
6¹ + 4 = 10 jagub 5-ga

Niisiis, P (1) vastab tõele

Sissejuhatus:

Oletame, et P (k) on tõene, nimelt:
6^k + 4 jagub 5-ga, k N

See näitab, et ka P (k + 1) on tõene, st:
6^{k + 1} + 4 jagub 5-ga.

6^{k + 1} + 4 = 6(6^k)+ 4
6^{k + 1} + 4 = 5(6^k) + 6^k + 4

Põhjus 5 (6^k) jagub arvudega 5 ja 6^k + 4 jagub 5-ga, seega 5 (6^k) + 6^k + 4 jagub ka 5-ga.

Niisiis, P (k + 1) on tõene.

Matemaatilise induktsiooni põhimõttest lähtuvalt on ilmne, et 6ⁿ + 4 jagub 5-ga iga n loodusarvu korral.

Täisarvud a jagatakse täisarvudega b kui leitakse täisarv m nii see juhtub a = bm.

Näiteks "10 jagub 5-ga" on tõene, kuna on täisarvu m = 2, nii et 10 = 5,2.

Seetõttu võime väite "10 jagub 5-ga" kirjutada järgmiselt: "10 = 5m, m täisarvu jaoks"

Eespool toodud kontseptsiooni põhjal saab jagatavuse tõendi lahendada ka järgmise meetodi abil.

Näide 4:

Tõestage n³ + 2n jagub 3-ga iga n loodusarvu korral

Vastus:

P (n): n³ + 2n = 3m, kus m ZZ

Tõestame, et P (n) on tõene iga n kohta NN

Esialgne samm:

See näitab, et P (1) on tõene
1³ + 2.1 = 3 = 3.1

Niisiis, P (1) vastab tõele

Sissejuhatus:

Oletame, et P (k) on tõene, nimelt:
k³ + 2k = 3m, k NN

See näitab, et ka P (k + 1) on tõene, st:
(k + 1)³ + 2 (k + 1) = 3p, lk ZZ

(k + 1)³ + 2 (k + 1) = (k³ + 3 k² + 3k + 1) + (2k + 2)
(k + 1)³ + 2 (k + 1) = (k³ + 2k) + (3k² + 3 k + 3)
(k + 1)³ + 2 (k + 1) = 3 m + 3 (k² + k + 1)
(k + 1)³ + 2 (k + 1) = 3 (m + k² + k + 1)

Kuna m on täisarv ja k on loomulik arv, siis (m + k² + k + 1) on täisarv.

Näiteks p = (m + k² + k + 1), nii et:
(k + 1)³ + 2 (k + 1) = 3p, kus p ZZ

Niisiis, P (k + 1) on tõene

Eespool toodud matemaatilise induktsiooni kontseptsiooni põhjal on tõestatud, et n³ + 2n jagub 3-ga iga n loodusarvu korral.

Tõend ebavõrdsusest

Järgnevalt on toodud mõned sageli kasutatava ebavõrdsuse omadused, sealhulgas:

1. Transitiivsed omadused
a> b> c a> c või
a

2. a 0 ac a> b ja c> 0 ac> bc

3. a a> b a + c> b + c

Enne näiteküsimustesse jõudmist on parem, kui harjutame kõigepealt, kasutades ülaltoodud omadusi implikatsiooni näitamiseks "kui P (k) on tõene, siis on ka P (k + 1) tõene".

Näide 1:

P (k): 4k <2^k
P (k + 1): 4 (k + 1) <2^{k + 1}

Kui eeldatakse, et P (k) on tõene k 5 kohta, siis näidake, et ka P (k + 1) on tõene!

Pidage meeles, et meie eesmärk on näidata, nii et:
4 (k + 1) <2^{k + 1} = 2(2^k) = 2^k + 2^k (SIHT)

Alustame ülaltoodud ebavõrdsuse vasakpoolsest küljest järgmiselt:
4 (k + 1) = 4k + 4
4 (k + 1) <2^k + 4 (kuna 4k <2^k)
4 (k + 1) <2^k + 2^k (kuna 4 <4k <2^k)
4 (k + 1) = 2 (2^k)
4 (k + 1) = 2^{k + 1}

Transitiivsete omaduste põhjal võime järeldada, et 4 (k + 1) <2^{k + 1}

Miks 4k-st saab 2^k ?

Sest vastavalt omadusele 3 on meil lubatud lisada ebavõrdsuse mõlemad pooled sama arvuga.

Sest see ei muuda ebavõrdsuse tõeväärtust. Põhjus 4k <2^k tõene, mille tulemuseks on 4k + 4 <2^k +4 vastab ka tõele.

Kuidas me teame, et 4 tuleks muuta 2^k?

Pöörake tähelepanu sihtmärkidele.

Ajutine tulemus, mille saame, on 2^k + 4, samas kui meie eesmärk on 2^k + 2^k.

K 5 korral siis 4 <4k ja 4k <2^k mis on tõsi, seega 4 <2^k on ka tõsi (transitiivne omadus). Selle tulemuseks on 2^k + 4 < 2^k + 2^k tõene (omadus 3).

Näide 2:

Tõestage, et iga naturaalse arvu n 4 korral kasutage
3n <2ⁿ

Vastus:

P (n): 3n <2ⁿ

Tõestame, et P (n) kehtib n 4, n korral NN

Esialgne samm:

Näitab, et P (4) vastab tõele
3.4 = 12 < 2⁴ = 16

Niisiis, P (4) vastab tõele

Sissejuhatus

Oletame, et P (k) on tõene, nimelt:
3k <2^k, k 4

See näitab, et ka P (k + 1) on tõene, st:
3 (k + 1) <2^{k + 1}

3 (k + 1) = 3k + 3
3 (k + 1) <2^k + 3 (kuna 3k <2^k)
3 (k + 1) <2^k + 2^k (kuna 3 <3k <2^k)
3 (k + 1) = 2 (2^k)
3 (k + 1) = 2^{k + 1}

Niisiis, P (k + 1) on ka tõsi.

Matemaatilise induktsiooni kontseptsiooni põhjal on tõestatud, et P (n) kehtib iga loodusliku arvu n 4 puhul.

Näide 3:

Tõestage, et iga naturaalse arvu n 2 korral kasutage 3ⁿ > 1 + 2n

Vastus:

P (n): 3ⁿ > 1 + 2n

Tõestame, et P (n) kehtib n 2, n korral NN

Esialgne samm:

Näitab, et P (2) on tõene, nimelt:
3² = 9 > 1 + 2.2 = 5

Niisiis, P (1) vastab tõele

Sissejuhatus:

Oletame, et P (k) on tõene, nimelt:
3^k > 1 + 2k, k 2

See näitab, et ka P (k + 1) on tõene, st
3^{k + 1} > 1 + 2 (k + 1)

3^{k + 1} = 3(3^k)
3^{k + 1} > 3 (1 + 2k) (kuna 3^k > 1 + 2k)
3^{k + 1} = 3 + 6k
3^{k + 1} > 3 + 2k (kuna 6k> 2k)
3^{k + 1} = 1 + 2k + 2
3^{k + 1} = 1 + 2 (k + 1)

Niisiis, P (k + 1) on ka tõsi

Matemaatilise induktsiooni kontseptsiooni põhjal on tõestatud, et P (n) kehtib iga loodusliku arvu n 2 korral.

Näide 4:

Tõestage, et iga naturaalse arvu n 5 korral on 2n 3 <2^n-2

Vastus:

P (n): 2n3 <2^n-2

Tõestame, et P (n) kehtib n 5, n kohta NN

Esialgne samm:

Näidatakse, et P (5) on tõene
2.5 − 3 = 7 < 2^5-2 = 8

Niisiis, P (1) vastab tõele

Induktsioonietapp:

Oletame, et P (k) on tõene, nimelt:
2k 3 <2^k-2, k 5

See näitab, et ka P (k + 1) on tõene, st:
2 (k + 1) 3 <2^{k + 1-2}

2 (k + 1) 3 = 2k + 2 3
2 (k + 1) 3 = 2k 3 + 2
2 (k + 1) 3 <2^k-2 + 2 (põhjus 2k 3 <2^k-2)
2 (k + 1) 3 <2^k-2 + 2^k-2 (põhjus 2 <2k 3 <2^k-2)
2 (k + 1) 3 = 2 (2^k-2)
2 (k + 1) 3 = 2^{k + 1-2}

Niisiis, P (k + 1) on ka tõsi

Matemaatilise induktsiooni kontseptsiooni põhjal on tõestatud, et P (n) kehtib iga loodusliku arvu n 5 puhul.

Näide 5:

Tõestage iga naturaalse arvu n 4 kohta ja rakendage (n + 1)! > 3ⁿ

Vastus:

P (n): (n + 1)! > 3ⁿ

Tõestame, et P (n) kehtib n 4, n korral NN

Esialgne samm:

Näitab, et P (4) on tõene
(4 + 1)! > 3⁴
vasak külg: 5! = 5.4.3.2.1 = 120
parem külg: 3⁴ = 81

Niisiis, P (1) vastab tõele
Sissejuhatus:

Oletame, et P (k) on tõene, nimelt:

(k + 1)! > 3^k, k 4

Näitame, et ka P (k + 1) on tõene, s.t.
(k + 1 + 1)! > 3^{k + 1}

(k + 1 + 1)! = (k + 2)!
(k + 1 + 1)! = (k + 2) (k + 1)!
(k + 1 + 1)! > (k + 2) (3^k) (põhjus (k + 1)! > 3^k)
(k + 1 + 1)! > 3(3^k) (põhjus k + 2> 3)
(k + 1 + 1)! = 3^{k + 1}

Niisiis, P (k + 1) on ka tõsi.

Matemaatilise induktsiooni kontseptsiooni põhjal on tõestatud, et P (n) kehtib iga loodusliku arvu n 4 puhul.

Seega lühike ülevaade, mille seekord saame edasi anda. Loodetavasti saab ülaltoodud ülevaadet kasutada õppematerjalina.