Matemaatiline induktsioon

Vali väide iga täisarvu n kohta. Iga allolev doomino on üks n. Doomino värv näitab, kas väide seal otseselt kontrollides kehtib. Nool doominost on induktsiooni samm n-ist n + 1-ni. Vaid tõene baasdoomino koos katkematu noolte jadaga moodustab tõestuse. Kõik doominod, milleni see jada ulatub, kukuvad ümber.

Näidisarvutus — Matemaatiline induktsioon

Samm 1 juurest 2 juurde	katkeb
Esimene väär n, kuni 12	2

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Matemaatiline induktsioon

Matemaatiline induktsioon tõestab väite P(n) iga täisarvu n jaoks alates mingist väärtusest n₀ kahe osa abil. Induktsiooni baas on otseselt kontrollitud P(n₀) ja induktsiooni samm on arutelu selle kohta, et P(k) tagab P(k + 1) kehtivuse iga k ≥ n₀ korral. Koos katavad need kõik n-i väärtused, sarnaselt langevatele doominokividele, mis üksteist pikali lükkavad.

Mida iga sümbol tähendab

P(n): väide n-i kohta; iga n-i korral on see kas tõene või väär
n₀: induktsiooni baas, millest tõestus algab ja mida kontrollitakse käsitsi
k: üldine n-i väärtus sammu sees: arutelu eeldab, et P(k) kehtib ja peab jõudma tulemuseni P(k + 1)

Kust valem tuleb

Miks neist kahest osast piisab. Oletame, et baas kehtib ja samm toimib iga k ≥ n₀ korral, kuid P on kuskil alates n₀-st ikkagi väär. Nende n-ide hulgas, kus see on väär, peab leiduma vähim. Nimetame selle m-iks. See vähim väärtus ei saa olla n₀, sest P(n₀) me just kontrollisime. Seega m − 1 ≥ n₀. Lisaks on P(m − 1) tõene, sest m oli teadupärast kõige esimene koht, kus väide murdus. Nüüd annab aga induktsiooni samm meile P(m), mis on teravas vastuolus eeldustega, et P(m) on väär. Järelikult ei eksisteeri ühtegi kohta, kus väide ei kehtiks. Mõlemal tõestuse osal on oma selge roll. Ilma baasita võiks m olla vabalt n₀. Kui aga ühesainsas kohas k samm puuduks, võiks m olla lihtsalt k + 1.
Miks pidi n² + n + 41 läbi kukkuma. Kohal n = 40 liituvad esimesed kaks liiget, 40² + 40 = 40 × 41. Nii saame 40² + 40 + 41 = 40 × 41 + 41 = 41 × 41. Kui n = 41, on iga liige 41 kordne ja koguväärtus seega 41 × 43. See seaduspära ulatub tegelikult palju kaugemale. Ükski täisarvuliste kordajatega mittekonstantne polünoom ei saa anda tulemuseks ainult algarve, ükskõik kui palju ta neid järjest ka ei toodaks (Lehman, Leighton ja Meyer tõestavad selle oma 1.25. ülesandes). Seega ei saanud selle väite jaoks mingit induktsiooni sammu kunagi eksisteerida.
2ⁿ > n² iga n ≥ 5 korral, korrektselt vormistatuna. Baas: 2⁵ = 32 > 25 = 5². Samm: olgu k ≥ 5 ja eeldame, et 2ᵏ > k². Siis 2ᵏ⁺¹ = 2 · 2ᵏ > 2k² = k² + k². Kuna k ≥ 5, siis k² ≥ 5k = 2k + 3k > 2k + 1. Sellest tulenevalt 2k² > k² + 2k + 1 = (k + 1)². Järelikult 2ᵏ⁺¹ > (k + 1)², mis ongi täpselt P(k + 1). Samm ise nõuab tegelikult vaid tingimust k ≥ 3. Baas pidi olema 5, kuna P(2), P(3) ja P(4) on kõik väärad.

Nelikümmend tõest juhtu, seejärel 41 × 41 🖖

Vajuta n² + n + 41. Väärtused 41, 43, 47, 53, 61, … on algarvud iga n korral vahemikus 0 kuni 39, kokku nelikümmend järjest. Kohal n = 40 on väärtus aga 1 681 = 41 × 41. Lähemal vaatlusel on see etteaimatav: 40² + 40 + 41 = 40 × 41 + 41. Graafikul puuduvad nooled, sest puudub induktsiooni samm. Teadmine, et p(39) = 1 601 on algarv, ei ütle midagi p(40) kohta, mis on p(39) + 80. Esimesest tuhandest väärtusest 581 on algarvud. Just seetõttu tundub see seaduspära nii veenev.

Samm väite 2ⁿ > n² jaoks toimib alates k = 3; väide ise alates n = 5 🖖

Vajuta 2ⁿ > n² alates 1. Baas kehtib, kuna 2 > 1. Samm ütleb, et kui 2ᵏ > k², siis 2ᵏ⁺¹ > 2k². Tingimus 2k² ≥ (k + 1)² on tõene täpselt siis, kui k² ≥ 2k + 1. See kehtib alates k = 3. Seega n₀ = 1 juurest alustades on nooled väärtustelt 1 ja 2 katkenud. Väide ongi väärtustel 2, 3 ja 4 väär. Nooled väärtustelt 3 ja 4 seevastu toimivad, kuigi P(3) ja P(4) on mõlemad väärad. Korrektne samm, mille taga on väär doomino, ei lükka midagi edasi. Vajuta 2ⁿ > n² alates 5 ning samad nooled tõestavad väite iga n korral alates viiendast.

Hobuste tõestus on õige igal sammul peale ühe 🖖

Vajuta Hobused. Samm võtab n + 1 hobust, rakendab väidet esimese n ja viimase n peal ning ühendab nad nende hobuste kaudu, kes on rühmadel ühised. Alates n = 2 see kõik toimib ja iga sealt algav nool on pidev. Vahemikus 1 kuni 2 on mõlemas rühmas aga vaid üks hobune ja neil puuduvad ühised hobused. Arutelu kukub läbi ainsas kohas, kus seda päriselt vaja on. Kui valida baasiks hoopis 5, toimib iga samm ideaalselt. Samas on P(5) väär ja nii puudub ahelal algtõuge.

Ülesanne täielikult lahendatud

Kust alates jääb 2ⁿ püsivalt suuremaks kui n³? 4 sammu
Tõesta, et 2ⁿ > n³ iga piisavalt suure n-i korral. Sammu on lihtne kirja panna. Kus see aga toimima hakkab ja milline peaks olema baas?

Ava see ülesanne tööriistas
1. Eelduseks on P(k): 2ᵏ > k³. Kahekordistamine on siin ainus võimalik samm:
  
  $2^{k} > k^{3} \Rightarrow 2^{k + 1} = 2 \cdot 2^{k} > 2 k^{3}$
2. Seega samm toimib, kui 2k³ ≥ (k + 1)³. Jaga mõlemad pooled läbi k³-ga:
  
  $2 k^{3} \geq (k + 1)^{3} ⟺ (1 + \frac{1}{k})^{3} \leq 2 ⟺ k \geq \frac{1}{3 2 - 1} = 3.847$
3. Samm toimib alates k = 4, mitte 3-st:
  
  $k = 3 : 2 \cdot 27 = 54 < 64 = 4^{3}, k = 4 : 2 \cdot 64 = 128 \geq 125 = 5^{3}$
4. Väide ise on aga väär vahemikus n = 2 kuni n = 9. Baasiks on esimene n, kus see taas kehtib:
  
  $2^{9} = 512 < 729 = 9^{3}, 2^{10} = 1, 024 > 1, 000 = 1 0^{3}$
Vastus

2ⁿ > n³ kehtib iga n ≥ 10 korral ning lisaks punktides n = 0 ja n = 1. Kuna samm toimib alates k = 4, peitub vahemikus k = 4 kuni k = 9 väära väite taga tegelikult korrektne samm. See on täpselt sama olukord nagu siinsel lehel väärtustel 3 ja 4 väitega 2ⁿ > n². Võrdlemiseks vajuta 2ⁿ > n² alates 5.

$2^{n} > n^{3} for every n \geq 10 (and n = 0, 1); step from k = 4, base n_{0} = 10$

Õpitee

Tõestusmeetodid

Allikad (3)

Both of this page's broken arguments, worked through: n² + n + 41 prime through n = 39 and 41·41 at n = 40 (§1.1), and the horses, whose failure the text pins to the one step P(1) → P(2) (§5.1): E. Lehman, F. T. Leighton and A. R. Meyer, Mathematics for Computer Science, MIT, revised 6 June 2018, §1.1 and §5.1.
The primes n² + n + 41 takes, with the forty consecutive prime values from n = 0 to 39: OEIS Foundation, "A005846: Primes of the form k² + k + 41", The On-Line Encyclopedia of Integer Sequences.
Where the horses come from: George Pólya posed the argument as an induction exercise in 1954: ProofWiki, "All Horses are the Same Colour/Historical Note", citing G. Pólya, Induction and Analogy in Mathematics (Princeton University Press, 1954).

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.