Primjeri matematičke indukcije rješenja za lutke. Primjena metode matematičke indukcije u rješavanju problema

Da biste to učinili, prvo provjerite istinitost izjave broj 1 - indukciona baza, a zatim se dokazuje da ako je tvrdnja sa brojem tačna n, tada je tačna i sljedeća izjava sa brojem n + 1 - korak indukcije, ili indukcijski prijelaz.

Dokaz indukcijom se može jasno predstaviti u obliku tzv domino princip. Neka bilo koji broj domino pločica bude postavljen u nizu na način da svaka domino pločica prilikom pada nužno prevrne domino kamen koji slijedi (ovo je induktivni prijelaz). Zatim, ako gurnemo prvu kost (ovo je osnova indukcije), onda će sve kosti u redu pasti.

Logična osnova za ovu metodu dokazivanja je tzv aksiom indukcije, peti od Peanovih aksioma koji definiraju prirodne brojeve. Ispravnost metode indukcije je ekvivalentna činjenici da u bilo kojem podskupu prirodnih brojeva postoji minimalni element.

Postoji i varijacija, takozvani princip potpune matematičke indukcije. Evo njegove stroge formulacije:

Princip potpune matematičke indukcije je također ekvivalentan aksiomu indukcije u Peanovim aksiomima.

Primjeri

Zadatak. Da to dokažem, šta god da je prirodno n i pravi q≠ 1 vrijedi jednakost

Dokaz. Indukcija uključena n.

Baza, n = 1:

Tranzicija: Hajde da se pretvaramo

,

Q.E.D.

Komentar: tačnost iskaza P n u ovom dokazu - isto što i istina jednakosti

vidi takođe

Varijacije i generalizacije

Književnost

• N. Ya. Vilenkin Indukcija. Kombinatorika. Priručnik za nastavnike. M., Prosveta, 1976.-48 str.
• L. I. Golovina, I. M. Yaglom Uvod u geometriju, “Popularna predavanja iz matematike”, broj 21, Fizmatgiz 1961.-100 str.
• R. Courant, G. Robbins"Šta je matematika?" Poglavlje I, § 2.
• I. S. Sominsky Metoda matematičke indukcije. “Popularna predavanja iz matematike”, broj 3, Izdavačka kuća “Nauka” 1965.-58 str.

Wikimedia fondacija. 2010.

Pogledajte šta je "Metoda matematičke indukcije" u drugim rječnicima:

Matematička indukcija u matematici je jedan od metoda dokazivanja. Koristi se za dokazivanje istinitosti određene tvrdnje za sve prirodne brojeve. Da bi se to uradilo, prvo se proverava istinitost tvrdnje sa brojem 1 na osnovu indukcije, a zatim... ... Wikipedia

Metoda izgradnje teorije, u kojoj se ona zasniva na određenim njenim odredbama - aksiomima ili postulatima - iz kojih se sve ostale odredbe teorije (teoreme) izvode rasuđivanjem, naziva se dokazi m i. Pravila prema Krimu...... Philosophical Encyclopedia

Indukcija (lat. inductio vođenje) je proces logičkog zaključivanja zasnovan na prelasku iz određene situacije u opštu. Induktivno zaključivanje povezuje određene premise sa zaključkom ne toliko kroz zakone logike, već više kroz neke ... ... Wikipedia

GENETSKA METODA- način definisanja sadržaja i suštine predmeta koji se proučava ne konvencijom, idealizacijom ili logičkim zaključkom, već proučavanjem njegovog porekla (na osnovu proučavanja razloga koji su doveli do njegovog nastanka, mehanizma formiranja). Široka...... Filozofija nauke: Pojmovnik osnovnih pojmova

Metoda konstruisanja naučne teorije u kojoj se zasniva na nekim početnim odredbama (sudovima) aksioma (vidi aksiom), ili postulata, iz kojih se moraju izvesti svi ostali iskazi ove nauke (teoreme (vidi teoremu)). ... Velika sovjetska enciklopedija

aksiomatska metoda- AKSIOMATSKA METODA (od grčkog axioma) je prihvaćen stav - metoda izgradnje naučne teorije, u kojoj se u dokazima koriste samo aksiomi, postulati i iskazi koji su prethodno iz njih izvedeni. Po prvi put jasno demonstrirano...... Enciklopedija epistemologije i filozofije nauke

Jedna od metoda teorijske greške za procjenu nepoznatih veličina iz rezultata mjerenja koji sadrže slučajne greške. N.K.M. se također koristi za aproksimaciju reprezentacije date funkcije drugim (jednostavnijim) funkcijama i često se ispostavi da je... Mathematical Encyclopedia

Matematička indukcija je jedna od metoda matematičkog dokaza, koja se koristi za dokazivanje istinitosti određene tvrdnje za sve prirodne brojeve. Da biste to učinili, prvo provjerite ... Wikipedia

Ovaj izraz ima druga značenja, vidi Indukcija. Indukcija (lat. inductio vođenje) je proces logičkog zaključivanja zasnovan na prelasku iz određene situacije u opštu. Induktivni zaključak povezuje određene premise... ... Wikipedia

Koristeći metodu matematičke indukcije, dokazati to za bilo koju prirodnu n važe sljedeće jednakosti:
A) ;
b) .

Rješenje.

a) Kada n= 1 jednakost je tačna. Uz pretpostavku valjanosti jednakosti na n, pokažimo njegovu valjanost čak i kada n+ 1. Zaista,

Q.E.D.

b) Kada n= 1 validnost jednakosti je očigledna. Od pretpostavke njegove valjanosti na n trebalo bi

S obzirom na jednakost 1 + 2 + ... + n = n(n+ 1)/2, dobijamo

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

tj. izjava je tačna i kada n + 1.

Primjer 1. Dokažite sljedeće jednakosti

Gdje n O N.

Rješenje. a) Kada n= 1 jednakost će imati oblik 1=1, dakle, P(1) je tačno. Pretpostavimo da je ta jednakost tačna, odnosno da vrijedi

. To je potrebno provjeriti (dokazati).P(n+ 1), tj istinito. Budući da (koristeći hipotezu indukcije) shvatamo da je, P(n+ 1) je tačna izjava.

Dakle, prema metodi matematičke indukcije, originalna jednakost vrijedi za bilo koju prirodnu n.

Napomena 2. Ovaj primjer je mogao biti riješen drugačije. Zaista, zbir je 1 + 2 + 3 + ... + n je zbir prvog n termini aritmetičke progresije sa prvim članom a 1 = 1 i razlika d= 1. Na osnovu dobro poznate formule , dobijamo

b) Kada n= 1 jednakost će imati oblik: 2 1 - 1 = 1 2 ili 1=1, tj. P(1) je tačno. Pretpostavimo da je jednakost

1 + 3 + 5 + ... + (2n - 1) = n 2 i dokazati da se to dešavaP(n + 1): 1 + 3 + 5 + ... + (2n - 1) + (2(n + 1) - 1) = (n+ 1) 2 ili 1 + 3 + 5 + ... + (2 n - 1) + (2n + 1) = (n + 1) 2 .

Koristeći hipotezu indukcije, dobijamo

1 + 3 + 5 + ... + (2n - 1) + (2n + 1) = n 2 + (2n + 1) = (n + 1) 2 .

dakle, P(n+ 1) je tačno i stoga je tražena jednakost dokazana.

Napomena 3. Ovaj primjer se može riješiti (slično kao i prethodni) bez korištenja metode matematičke indukcije.

c) Kada n= 1 jednakost je tačna: 1=1. Pretpostavimo da je jednakost tačna

i pokaži to odnosno istinaP(n) implicira istinuP(n+ 1). stvarno, i od 2 n 2 + 7 n + 6 = (2 n + 3)(n+ 2), dobijamo i, prema tome, originalna jednakost vrijedi za bilo koju prirodnun.

d) Kada n= 1 jednakost je tačna: 1=1. Pretpostavimo da se to dešava

i to ćemo dokazati

stvarno,

e) Odobrenje P(1) tačno: 2=2. Pretpostavimo da je jednakost

je tačno, a mi ćemo dokazati da to implicira jednakost stvarno,

Prema tome, originalna jednakost vrijedi za bilo koju prirodnu n.

f) P(1) istina: 1/3 = 1/3. Neka bude jednakosti P(n):

. Pokažimo da posljednja jednakost implicira sljedeće:

Zaista, s obzirom na to P(n) drži, dobijamo

Dakle, jednakost je dokazana.

g) Kada n= 1 imamo a + b = b + a i stoga je jednakost pravedna.

Neka vrijedi Newtonova binomna formula za n = k, to je,

Onda Koristeći jednakost dobijamo

Primjer 2. Dokazati nejednakosti

a) Bernulijeva nejednakost: (1 + a) n ≥ 1 + n a , a > -1, n O N.

b) x 1 + x 2 + ... + x n ≥ n, Ako x 1 x 2 · ... · x n= 1 i x i > 0, .

c) Cauchyjeva nejednakost u odnosu na aritemetičku sredinu i geometrijsku sredinu Gdje x i > 0, , n ≥ 2.

d) grijeh 2 n a + cos 2 n a ≤ 1, n O N.

e)

f) 2 n > n 3 , n O N, n ≥ 10.

Rješenje. a) Kada n= 1 dobijamo pravu nejednakost

1 + a ≥ 1 + a . Pretpostavimo da postoji nejednakost

(1 + a) n ≥ 1 + n a

(1)

a mi ćemo pokazati da se onda to dešava i(1 + a) n + 1 ≥ 1 + (n+ 1)a .

Zaista, pošto a > -1 implicira a + 1 > 0, onda množenjem obe strane nejednakosti (1) sa (a + 1) dobijamo

(1 + a) n(1 + a) ≥ (1 + n a )(1 + a) ili (1 + a) n + 1 ≥ 1 + (n+ 1)a + n a 2 Od n a 2 ≥ 0, dakle(1 + a) n + 1 ≥ 1 + (n+ 1)a + n a 2 ≥ 1 + ( n+ 1)a .

Dakle, ako P(n) je onda tačno P(n+ 1) je istinito, dakle, prema principu matematičke indukcije, Bernoullijeva nejednakost je istinita.

b) Kada n= 1 dobijamo x 1 = 1 i stoga x 1 ≥ 1 tj P(1) je poštena izjava. Pretvarajmo se to P(n) je tačno, odnosno ako je adica, x 1 ,x 2 ,...,x n - n pozitivni brojevi čiji je proizvod jednak jedan, x 1 x 2 ·...· x n= 1, i x 1 + x 2 + ... + x n ≥ n.

Pokažimo da ova rečenica podrazumijeva istinitost sljedećeg: ako x 1 ,x 2 ,...,x n ,x n+1 - (n+ 1) pozitivni brojevi takvi da x 1 x 2 ·...· x n · x n+1 = 1, onda x 1 + x 2 + ... + x n + x n + 1 ≥n + 1.

Razmotrite sljedeća dva slučaja:

1) x 1 = x 2 = ... = x n = x n+1 = 1. Tada je zbir ovih brojeva ( n+ 1), i tražena nejednakost je zadovoljena;

2) barem jedan broj je različit od jednog, neka je, na primjer, veći od jedan. Onda, pošto x 1 x 2 · ... · x n · x n+ 1 = 1, postoji barem još jedan broj različit od jednog (tačnije, manji od jedan). Neka x n+ 1 > 1 i x n < 1. Рассмотрим n pozitivni brojevi

x 1 ,x 2 ,...,x n-1 ,(x n · x n+1). Proizvod ovih brojeva jednak je jedan, a prema hipotezi, x 1 + x 2 + ... + x n-1 + x n x n + 1 ≥ n. Posljednja nejednakost se prepisuje na sljedeći način: x 1 + x 2 + ... + x n-1 + x n x n+1 + x n + x n+1 ≥ n + x n + x n+1 ili x 1 + x 2 + ... + x n-1 + x n + x n+1 ≥ n + x n + x n+1 - x n x n+1 .

Zbog

(1 - x n)(x n+1 - 1) > 0, onda n + x n + x n+1 - x n x n+1 = n + 1 + x n+1 (1 - x n) - 1 + x n =
= n + 1 + x n+1 (1 - x n) - (1 - x n) = n + 1 + (1 - x n)(x n+1 - 1) ≥ n+ 1. Dakle, x 1 + x 2 + ... + x n + x n+1 ≥ n+1, odnosno ako P(n) je onda tačnoP(n+ 1) pošteno. Nejednakost je dokazana.

Napomena 4. Znak jednakosti vrijedi ako i samo ako x 1 = x 2 = ... = x n = 1.

c) Neka x 1 ,x 2 ,...,x n- proizvoljni pozitivni brojevi. Uzmite u obzir sljedeće n pozitivni brojevi:

Pošto je njihov proizvod jednak jedan: prema prethodno dokazanoj nejednakosti b), slijedi da gdje

Napomena 5. Jednakost vrijedi ako i samo ako x 1 = x 2 = ... = x n .

d) P(1) je fer izjava: sin 2 a + cos 2 a = 1. Pretpostavimo to P(n) je istinita izjava:

Grijeh 2 n a + cos 2 n a ≤ 1 i pokazati šta se dešavaP(n+ 1). stvarno, grijeh 2( n+ 1) a + cos 2( n+ 1) a = sin 2 n a sin 2 a + cos 2 n a cos 2 a< sin 2n a + cos 2 n a ≤ 1 (ako je sin 2 a ≤ 1, tada je cos 2 a < 1, и обратно: если cos 2 a ≤ 1, zatim sin 2 a < 1). Таким образом, для любого n O N grijeh 2 n a + cos 2 n ≤ 1 i znak jednakosti se postiže samo kadan = 1.

e) Kada n= 1 izjava je tačna: 1< 3 / 2 .

Pretpostavimo to i to ćemo dokazati

Zbog
razmatrati P(n), dobijamo

f) Uzimajući u obzir napomenu 1, provjerimo P(10): 2 10 > 10 3, 1024 > 1000, dakle, za n= 10 izjava je tačna. Pretpostavimo da je 2 n > n 3 (n> 10) i dokazati P(n+ 1), odnosno 2 n+1 > (n + 1) 3 .

Od kada n> 10 imamo ili , slijedi to

2n 3 > n 3 + 3n 2 + 3n+ 1 ili n 3 > 3n 2 + 3n + 1. S obzirom na nejednakost (2 n > n 3), dobijamo 2 n+1 = 2 n·2 = 2 n + 2 n > n 3 + n 3 > n 3 + 3n 2 + 3n + 1 = (n + 1) 3 .

Dakle, prema metodi matematičke indukcije, za bilo koju prirodnu n O N, n≥ 10 imamo 2 n > n 3 .

Primjer 3. Dokažite to bilo kome n O N

Rješenje. a) P(1) je tačan iskaz (0 je podijeljeno sa 6). Neka P(n) je pošteno, tj n(2n 2 - 3n + 1) = n(n - 1)(2n- 1) je djeljiv sa 6. Pokažimo da se tada javlja P(n+ 1), odnosno ( n + 1)n(2n+ 1) je djeljiv sa 6. Zaista, pošto

I kako n(n - 1)(2 n- 1) i 6 n 2 su djeljive sa 6, onda je njihov zbirn(n + 1)(2 n+ 1) je djeljiv sa 6.

dakle, P(n+ 1) je poštena izjava, i stoga n(2n 2 - 3n+ 1) djeljivo sa 6 za bilo koji n O N.

b) Hajde da proverimo P(1): 6 0 + 3 2 + 3 0 = 11, dakle, P(1) je poštena izjava. Treba dokazati da ako 6 2 n-2 + 3 n+1 + 3 n-1 je podijeljeno sa 11 ( P(n)), zatim 6 2 n + 3 n+2 + 3 n također djeljiv sa 11 ( P(n+ 1)). Zaista, pošto

6 2n + 3 n+2 + 3 n = 6 2n-2+2 + 3 n+1+1 + 3 n-1+1 = = 6 2 6 2 n-2 + 3 3 n+1 + 3 3 n-1 = 3·(6 2 n-2 + 3 n+1 + 3 n-1) + 33 6 2 n-2 i slično 6 2 n-2 + 3 n+1 + 3 n-1 i 33 6 2 n-2 su djeljive sa 11, tada je njihov zbir 6 2n + 3 n+2 + 3 n je djeljiv sa 11. Tvrdnja je dokazana. Indukcija u geometriji

Primjer 4. Izračunaj stranu tačne 2 n-trougao upisan u krug poluprečnika R.

Metoda dokaza zasnovana na Peanovom aksiomu 4 koristi se za dokazivanje mnogih matematičkih svojstava i različitih tvrdnji. Osnova za ovo je sljedeća teorema.

Teorema. Ako je izjava A(n) sa prirodnom varijablom n istina za n= 1 i iz činjenice da je istina za n = k, slijedi da je istina za sljedeći broj n=k, zatim izjava A(n) n.

Dokaz. Označimo sa M skup onih i samo onih prirodnih brojeva za koje je iskaz A(n) istinito. Tada iz uslova teoreme imamo: 1) 1 M; 2) kmkM. Odavde, na osnovu aksioma 4, zaključujemo da M =N, tj. izjava A(n) istina za sve prirodne n.

Metoda dokaza zasnovana na ovoj teoremi naziva se metodom matematičke indukcije, a aksiom je aksiom indukcije. Ovaj dokaz se sastoji iz dva dela:

1) dokazati da je iskaz A(n) istina za n= A(1);

2) pretpostaviti da je izjava A(n) istina za n = k, i na osnovu ove pretpostavke dokazati da je iskaz A(n) istina za n = k + 1, tj. da je izjava tačna A(k) A(k + 1).

Ako A( 1) A(k) A(k + 1) - istinita izjava, onda zaključuju da je izjava A(n) tačno za bilo koji prirodan broj n.

Dokaz metodom matematičke indukcije može početi ne samo potvrdom istinitosti tvrdnje za n= 1, ali i iz bilo kojeg prirodnog broja m. U ovom slučaju izjava A(n) biće dokazano za sve prirodne brojeve nm.

Problem: Dokažimo da je za bilo koji prirodan broj jednakost 1 + 3 + 5 … + (2 n- 1) = n.

Rješenje. Jednakost 1 + 3 + 5 … + (2 n- 1) = n je formula koja se može koristiti za pronalaženje zbroja prvih uzastopnih neparnih prirodnih brojeva. Na primjer, 1 + 3 + 5 + 7 = 4= 16 (zbir sadrži 4 člana), 1 + 3 + 5 + 7 + 9 + 11 = 6= 36 (zbir sadrži 6 članova); ako ovaj zbir sadrži 20 članova navedenog tipa, onda je jednak 20 = 400, itd. Kada smo dokazali istinitost ove jednakosti, moći ćemo pronaći zbir bilo kojeg broja članova navedenog tipa koristeći formulu.

1) Provjerimo istinitost ove jednakosti za n= 1. Kada n= 1 lijeva strana jednakosti se sastoji od jednog člana jednakog 1, desna strana je jednaka 1= 1. Kako je 1 = 1, onda za n= 1 ova jednakost je tačna.

2) Pretpostavimo da je ova jednakost tačna za n = k, tj. da je 1 + 3 + 5 + … + (2 k- 1) = k. Na osnovu ove pretpostavke dokazujemo da je to tačno za n = k + 1, tj. 1 + 3 + 5 + … + (2 k- 1) + (2(k + 1) - 1) = (k + 1).

Pogledajmo lijevu stranu posljednje jednakosti.

Po pretpostavci, zbir prvog k uslovi je jednak k i stoga 1 + 3 + 5 + … + (2 k- 1) + (2(k + 1) - 1) = 1 + 3 + 5 + … + (2k- 1) + (2k+ 1)=

= k+(2k + 1) = k+ 2k + 1. Izraz k+ 2k + 1 je identično jednako izrazu ( k + 1).

Dakle, istinitost ove jednakosti za n = k + 1 je dokazano.

Dakle, ova jednakost vrijedi za n= 1 i iz njegove istine za n = k mora biti istina za n = k + 1.

Ovo dokazuje da ova jednakost vrijedi za bilo koji prirodan broj.

Koristeći metodu matematičke indukcije, možete dokazati istinitost ne samo jednakosti, već i nejednakosti.

Zadatak. Dokaži da, gde nN.

Rješenje. Provjerimo istinitost nejednakosti na n= 1. Imamo - pravu nejednakost.

Pretpostavimo da je nejednakost tačna za n = k, one. - istinska nejednakost. Dokažimo, na osnovu pretpostavke, da je i za n = k + 1, tj. (*).

Transformirajmo lijevu stranu nejednakosti (*), uzimajući u obzir da: .

Ali , što znači .

Dakle, ova nejednakost je tačna za n= 1, i iz činjenice da je nejednakost tačna za neke n= k, otkrili smo da je to istina i za n= k + 1.

Dakle, koristeći aksiom 4, dokazali smo da je ova nejednakost tačna za bilo koji prirodan broj.

Druge tvrdnje se mogu dokazati metodom matematičke indukcije.

Zadatak. Dokažite da je za bilo koji prirodan broj tvrdnja tačna.

Rješenje. Provjerimo istinitost izjave kada n= 1: -tačna izjava.

Pretpostavimo da je ova izjava tačna za n = k: . Pokažimo, koristeći ovo, istinitost iskaza kada n = k + 1: .

Transformirajmo izraz: . Hajde da nađemo razliku k I k+ 1 članova. Ako se ispostavi da je rezultujuća razlika višekratnik 7, a po pretpostavci je oduzetak djeljiv sa 7, tada je i minuend višekratnik 7:

Proizvod je višekratnik 7, dakle, i .

Dakle, ova izjava je tačna za n= 1 i iz njegove istine za n = k mora biti istina za n = k + 1.

Ovo dokazuje da je ova izjava tačna za bilo koji prirodan broj.

Zadatak. Dokažite to za bilo koji prirodan broj n 2 izjava (7-1)24 je tačna.

Rješenje. 1) Provjerimo istinitost tvrdnje kada n= 2: - tačan iskaz.

Istinsko znanje u svakom trenutku se zasnivalo na uspostavljanju obrasca i dokazivanju njegove istinitosti u određenim okolnostima. Tokom tako dugog perioda postojanja logičkog zaključivanja, date su formulacije pravila, a Aristotel je čak sastavio listu „ispravnih rasuđivanja“. Istorijski gledano, bilo je uobičajeno da se svi zaključci dijele na dvije vrste - od konkretnih do višestrukih (indukcija) i obrnuto (dedukcija). Treba napomenuti da vrste dokaza od posebnog do opšteg i od opšteg do posebnog postoje samo u sprezi i ne mogu se menjati.

Indukcija u matematici

Izraz "indukcija" ima latinske korijene i doslovno se prevodi kao "vođenje". Nakon detaljnijeg proučavanja, može se istaknuti struktura riječi, odnosno latinski prefiks - in- (označava usmjerenu radnju prema unutra ili biti unutra) i -duction - uvod. Vrijedi napomenuti da postoje dvije vrste - potpuna i nepotpuna indukcija. Pun oblik karakteriziraju zaključci izvučeni iz proučavanja svih objekata određene klase.

Nepotpuni - zaključci koji se odnose na sve predmete u razredu, ali se donose na osnovu proučavanja samo nekih jedinica.

Potpuna matematička indukcija je zaključak zasnovan na opštem zaključku o čitavoj klasi bilo kojih objekata koji su funkcionalno povezani odnosima prirodnog niza brojeva na osnovu poznavanja ove funkcionalne veze. U ovom slučaju, proces dokazivanja se odvija u tri faze:

• prvi dokazuje ispravnost stava matematičke indukcije. Primjer: f = 1, indukcija;
• sljedeća faza je zasnovana na pretpostavci da je pozicija važeća za sve prirodne brojeve. To jest, f=h je induktivna hipoteza;
• u trećoj fazi se dokazuje validnost pozicije za broj f=h+1, na osnovu ispravnosti položaja prethodne tačke - ovo je indukcijski prelaz, odnosno korak matematičke indukcije. Primjer je tzv. ako padne prvi kamen u nizu (osnova), onda padaju svi kamenovi u nizu (prijelaz).

I u šali i ozbiljno

Radi lakšeg razumijevanja, primjeri rješenja korištenjem metode matematičke indukcije predstavljeni su u obliku šaljivih zadataka. Ovo je zadatak “Učtivi red”:

• Pravila ponašanja zabranjuju muškarcu da se okrene ispred žene (u takvoj situaciji joj je dozvoljeno da ide naprijed). Na osnovu ove izjave, ako je posljednji u redu muškarac, onda su svi ostali muškarci.

Upečatljiv primjer metode matematičke indukcije je problem "bezdimenzijskog leta":

• Potrebno je dokazati da u minibus može stati bilo koji broj ljudi. Istina je da jedna osoba može bez poteškoća stati u vozilo (osnova). Ali bez obzira koliko je minibus pun, u njega će uvijek stati 1 putnik (indukcijski korak).

Poznati krugovi

Primjeri rješavanja problema i jednačina matematičkom indukcijom su prilično česti. Kao ilustraciju ovog pristupa, razmotrite sljedeći problem.

Stanje: na ravni ima h krugova. Potrebno je dokazati da se, za bilo koji raspored figura, karta koju formiraju može ispravno obojati u dvije boje.

Rješenje: kada je h=1 istinitost tvrdnje je očigledna, pa će se dokaz konstruisati za broj krugova h+1.

Prihvatimo pretpostavku da tvrdnja vrijedi za bilo koju kartu, a na ravni ima h+1 krugova. Uklanjanjem jednog od krugova iz ukupnog broja možete dobiti kartu ispravno obojenu u dvije boje (crna i bijela).

Prilikom vraćanja izbrisanog kruga, boja svake oblasti se mijenja u suprotnu (u ovom slučaju unutar kruga). Rezultat je karta ispravno obojena u dvije boje, što je trebalo dokazati.

Primjeri sa prirodnim brojevima

U nastavku je jasno prikazana primjena metode matematičke indukcije.

Primjeri rješenja:

Dokažite da je za bilo koji h tačna sljedeća jednakost:

1 2 +2 2 +3 2 +…+h 2 =h(h+1)(2h+1)/6.

1. Neka je h=1, što znači:

R 1 =1 2 =1(1+1)(2+1)/6=1

Iz ovoga slijedi da je za h=1 tvrdnja tačna.

2. Uz pretpostavku da je h=d, dobija se jednačina:

R 1 =d 2 =d(d+1)(2d+1)/6=1

3. Uz pretpostavku da je h=d+1, ispada:

R d+1 =(d+1) (d+2) (2d+3)/6

R d+1 = 1 2 +2 2 +3 2 +…+d 2 +(d+1) 2 = d(d+1)(2d+1)/6+ (d+1) 2 =(d( d+1)(2d+1)+6(d+1) 2)/6=(d+1)(d(2d+1)+6(k+1))/6=

(d+1)(2d 2 +7d+6)/6=(d+1)(2(d+3/2)(d+2))/6=(d+1)(d+2)( 2d+3)/6.

Time je dokazana valjanost jednakosti za h=d+1, pa je tvrdnja tačna za bilo koji prirodan broj, kao što je prikazano u primjeru rješenja matematičkom indukcijom.

Zadatak

Stanje: potreban je dokaz da je za bilo koju vrijednost h izraz 7 h -1 djeljiv sa 6 bez ostatka.

Rješenje:

1. Recimo h=1, u ovom slučaju:

R 1 =7 1 -1=6 (tj. podijeljeno sa 6 bez ostatka)

Dakle, za h=1 izjava je tačna;

2. Neka je h=d i 7 d -1 podijeljeno sa 6 bez ostatka;

3. Dokaz valjanosti tvrdnje za h=d+1 je formula:

R d +1 =7 d +1 -1=7∙7 d -7+6=7(7 d -1)+6

U ovom slučaju, prvi član je djeljiv sa 6 prema pretpostavci prve tačke, a drugi član je jednak 6. Tačna je tvrdnja da je 7 h -1 djeljivo sa 6 bez ostatka za bilo koje prirodno h.

Greške u rasuđivanju

Često se u dokazima koristi pogrešno zaključivanje zbog netačnosti korištenih logičkih konstrukcija. To se uglavnom dešava kada se naruši struktura i logika dokaza. Primjer pogrešnog zaključivanja je sljedeća ilustracija.

Zadatak

Stanje: potreban je dokaz da bilo koja gomila kamenja nije gomila.

Rješenje:

1. Recimo h=1, u ovom slučaju ima 1 kamen u gomili i tvrdnja je tačna (osnova);

2. Neka je tačno za h=d da gomila kamenja nije gomila (pretpostavka);

3. Neka je h=d+1, iz čega slijedi da pri dodavanju još jednog kamena set neće biti gomila. Zaključak se nameće da pretpostavka vrijedi za sve prirodne h.

Greška je u tome što ne postoji definicija koliko kamenja čini gomilu. Takav propust se u metodi matematičke indukcije naziva prenagljenom generalizacijom. Primjer to jasno pokazuje.

Indukcija i zakoni logike

Istorijski gledano, oni uvijek “hodaju ruku pod ruku”. Naučne discipline kao što su logika i filozofija opisuju ih u obliku suprotnosti.

Sa stanovišta zakona logike, induktivne definicije se oslanjaju na činjenice, a istinitost premisa ne određuje ispravnost rezultirajućeg iskaza. Često se zaključci dobijaju sa određenim stepenom vjerovatnoće i uvjerljivosti, koji se, naravno, moraju provjeriti i potvrditi dodatnim istraživanjem. Primjer indukcije u logici bi bio sljedeća izjava:

Suša je u Estoniji, suša u Letoniji, suša u Litvaniji.

Estonija, Letonija i Litvanija su baltičke države. U svim baltičkim državama vlada suša.

Iz primjera možemo zaključiti da se nova informacija ili istina ne može dobiti metodom indukcije. Sve na šta se može računati je neka moguća istinitost zaključaka. Štaviše, istinitost premisa ne garantuje iste zaključke. Međutim, ova činjenica ne znači da indukcija čami na marginama dedukcije: ogroman broj odredbi i naučnih zakona potkrepljuje se metodom indukcije. Primjer je ista matematika, biologija i druge nauke. To je uglavnom zbog metode potpune indukcije, ali u nekim slučajevima je primjenjiva i djelomična indukcija.

Časno doba indukcije omogućilo mu je da prodre u gotovo sve sfere ljudske aktivnosti - to je nauka, ekonomija i svakodnevni zaključci.

Uvođenje u naučnu zajednicu

Metoda indukcije zahtijeva skrupulozan stav, jer previše ovisi o broju dijelova proučavane cjeline: što je veći broj proučavan, to je rezultat pouzdaniji. Na osnovu ove karakteristike, naučni zakoni dobijeni indukcijom se dugo testiraju na nivou probabilističkih pretpostavki kako bi se izolovali i proučavali svi mogući strukturni elementi, veze i uticaji.

U nauci se induktivni zaključak zasniva na značajnim karakteristikama, sa izuzetkom slučajnih odredbi. Ova činjenica je važna u vezi sa specifičnostima naučnog saznanja. To se jasno vidi na primjerima indukcije u nauci.

U naučnom svijetu postoje dvije vrste indukcije (u vezi sa metodom proučavanja):

1. indukcija-selekcija (ili selekcija);
2. indukcija - isključivanje (eliminacija).

Prvi tip se razlikuje po metodičkom (savjesnom) odabiru uzoraka klase (potklase) iz njenih različitih područja.

Primjer ove vrste indukcije je sljedeći: srebro (ili soli srebra) pročišćavaju vodu. Zaključak je zasnovan na višegodišnjim zapažanjima (neka vrsta selekcije potvrda i opovrgavanja – selekcija).

Druga vrsta indukcije zasniva se na zaključcima koji uspostavljaju uzročne veze i isključuju okolnosti koje ne odgovaraju njenim svojstvima, a to su univerzalnost, pridržavanje vremenskog slijeda, nužnost i jednoznačnost.

Indukcija i dedukcija sa pozicije filozofije

Gledajući u prošlost, pojam indukcije prvi je spomenuo Sokrat. Aristotel je opisao primjere indukcije u filozofiji u približnijem terminološkom rječniku, ali pitanje nepotpune indukcije ostaje otvoreno. Nakon progona aristotelovskog silogizma, induktivna metoda se počela prepoznavati kao plodna i jedina moguća u prirodnoj nauci. Bekon se smatra ocem indukcije kao nezavisne specijalne metode, ali nije uspeo da odvoji indukciju od deduktivne metode, kako su zahtevali njegovi savremenici.

Indukciju je dalje razvio J. Mill, koji je induktivnu teoriju razmatrao iz perspektive četiri glavne metode: slaganje, razlika, ostaci i odgovarajuće promjene. Nije iznenađujuće da su danas navedene metode, kada se detaljno ispitaju, deduktivne.

Shvaćanje nedosljednosti teorija Bacona i Mill-a navelo je naučnike da proučavaju probabilističku osnovu indukcije. Međutim, i ovdje je bilo nekih ekstrema: činjeni su pokušaji da se svede indukcija na teoriju vjerovatnoće sa svim posljedicama koje su iz toga proizašle.

Indukcija dobija glas povjerenja kroz praktičnu primjenu u određenim predmetnim oblastima i zahvaljujući metričkoj tačnosti induktivne osnove. Primjer indukcije i dedukcije u filozofiji može se smatrati Zakonom univerzalne gravitacije. Na dan otkrića zakona, Njutn je mogao da ga potvrdi sa tačnošću od 4 procenta. A kada je provjerena više od dvije stotine godina kasnije, ispravnost je potvrđena s točnošću od 0,0001 posto, iako je provjera izvršena istim induktivnim generalizacijama.

Moderna filozofija posvećuje više pažnje dedukciji, koja je diktirana logičnom željom da se izvuče novo znanje (ili istine) iz onoga što je već poznato, bez pribjegavanja iskustvu ili intuiciji, već koristeći „čisto“ rasuđivanje. Kada se u deduktivnoj metodi pozivaju na istinite premise, u svim slučajevima izlaz je tačan iskaz.

Ova veoma važna karakteristika ne bi trebalo da zaseni vrednost induktivne metode. Budući da indukcija, zasnovana na dostignućima iskustva, postaje i sredstvo njegove obrade (uključujući generalizaciju i sistematizaciju).

Primjena indukcije u ekonomiji

Indukcija i dedukcija se dugo koriste kao metode za proučavanje privrede i predviđanje njenog razvoja.

Opseg upotrebe metode indukcije je prilično širok: proučavanje ispunjenosti predviđenih indikatora (profita, amortizacije, itd.) i opšta procjena stanja preduzeća; formiranje efikasne politike promocije preduzeća zasnovane na činjenicama i njihovim odnosima.

Isti metod indukcije korišćen je i u „Shewhartovim mapama“, gde se, pod pretpostavkom podele procesa na kontrolisane i nekontrolisane, navodi da je okvir kontrolisanog procesa neaktivan.

Treba napomenuti da se naučne zakonitosti potkrepljuju i potvrđuju metodom indukcije, a kako je ekonomija nauka koja često koristi matematičku analizu, teoriju rizika i statistiku, nije nimalo iznenađujuće što je indukcija na listi glavnih metoda.

Primjer indukcije i dedukcije u ekonomiji je sljedeća situacija. Povećanje cijena hrane (iz potrošačke korpe) i esencijalnih dobara tjera potrošača na razmišljanje o novonastalim visokim troškovima u državi (indukcija). Istovremeno, iz činjenice visokih cijena, pomoću matematičkih metoda, moguće je izvesti pokazatelje rasta cijena za pojedinačna dobra ili kategorije roba (odbitak).

Najčešće se rukovodeće osoblje, menadžeri i ekonomisti okreću metodi indukcije. Da bi se mogao sa dovoljnom istinitošću predvideti razvoj preduzeća, ponašanje na tržištu i posledice konkurencije, neophodan je induktivno-deduktivni pristup analizi i obradi informacija.

Jasan primjer uvođenja u ekonomiju u vezi s pogrešnim prosudbama:

• dobit kompanije smanjena za 30%;
  konkurentska kompanija je proširila svoju liniju proizvoda;
  ništa drugo se nije promijenilo;
• proizvodna politika konkurentske kompanije dovela je do smanjenja profita za 30%;
• stoga je potrebno provesti istu proizvodnu politiku.

Primjer je živopisna ilustracija kako nesposobna upotreba metode indukcije doprinosi propasti poduzeća.

Dedukcija i indukcija u psihologiji

Pošto postoji metoda, onda, logično, postoji i pravilno organizovano razmišljanje (da se koristi metoda). Psihologija kao nauka koja proučava mentalne procese, njihovo formiranje, razvoj, odnose, interakcije, obraća pažnju na „deduktivno“ mišljenje, kao jedan od oblika ispoljavanja dedukcije i indukcije. Nažalost, na stranicama psihologije na internetu praktično nema opravdanja za integritet deduktivno-induktivne metode. Iako se profesionalni psiholozi češće susreću s manifestacijama indukcije, odnosno pogrešnih zaključaka.

Primjer indukcije u psihologiji, kao ilustracija pogrešnih sudova, je izjava: moja majka vara, dakle, sve žene su varalice. Možete izvući još više "pogrešnih" primjera indukcije iz života:

• učenik je nesposoban za bilo šta ako dobije lošu ocjenu iz matematike;
• on je budala;
• on je pametan;
• mogu sve;

I mnogi drugi vrijednosni sudovi zasnovani na potpuno slučajnim i, ponekad, beznačajnim premisama.

Treba napomenuti: kada zabluda nečijeg prosuđivanja dostigne tačku apsurda, psihoterapeutu se pojavljuje granica rada. Jedan primjer uvođenja u službu kod specijaliste:

“Pacijent je potpuno siguran da je crvena boja opasna samo za njega u bilo kom obliku. Kao rezultat toga, osoba je isključila ovu shemu boja iz svog života - što je više moguće. Postoji mnogo mogućnosti za ugodan boravak kod kuće. Možete odbiti sve crvene predmete ili ih zamijeniti analozima napravljenim u drugoj shemi boja. Ali na javnim mjestima, na poslu, u prodavnici - to je nemoguće. Kada se pacijent nađe u stresnoj situaciji, svaki put doživi “plimu” potpuno različitih emocionalnih stanja, koja mogu predstavljati opasnost za druge.”

Ovaj primjer indukcije i nesvjesne indukcije naziva se "fiksne ideje". Ako se to dogodi mentalno zdravoj osobi, možemo govoriti o neorganiziranosti mentalne aktivnosti. Način da se riješite opsesivnih stanja može biti elementarni razvoj deduktivnog mišljenja. U drugim slučajevima sa takvim pacijentima rade psihijatri.

Gore navedeni primjeri indukcije ukazuju na to da vas “nepoznavanje zakona ne izuzima od posljedica (pogrešnih presuda)”.

Psiholozi, koji rade na temi deduktivnog razmišljanja, sastavili su listu preporuka osmišljenih da pomognu ljudima da savladaju ovu metodu.

Prva tačka je rješavanje problema. Kao što se može vidjeti, oblik indukcije koji se koristi u matematici može se smatrati „klasičnim“, a upotreba ove metode doprinosi „disciplini“ uma.

Sljedeći uvjet za razvoj deduktivnog mišljenja je širenje vidika (oni koji jasno misle jasno se izražavaju). Ova preporuka usmjerava “patnju” u riznice nauke i informacija (biblioteke, web stranice, obrazovne inicijative, putovanja, itd.).

Posebno treba spomenuti takozvanu „psihološku indukciju“. Ovaj izraz, iako ne često, može se naći na internetu. Svi izvori ne daju barem kratku formulaciju definicije ovog pojma, već se pozivaju na „primjere iz života“, a kao novu vrstu indukcije promiču ili sugestiju, ili neke oblike mentalne bolesti, ili ekstremna stanja ljudska psiha. Iz svega gore navedenog, jasno je da pokušaj da se izvede „novi termin“ zasnovan na lažnim (često neistinitim) premisa osuđuje eksperimentatora na dobijanje pogrešne (ili ishitrene) izjave.

Treba napomenuti da pozivanje na eksperimente iz 1960. godine (bez navođenja lokacije, imena eksperimentatora, uzorka ispitanika i, što je najvažnije, svrhe eksperimenta) izgleda, blago rečeno, neuvjerljivo, a izjava da mozak percipira informaciju zaobilazeći sve organe percepcije (u ovom slučaju bi se organski uklopila fraza „zahvaćen je“), navodi na razmišljanje o lakovjernosti i nekritičnosti autora izjave.

Umjesto zaključka

Nije uzalud da kraljica nauka, matematika, koristi sve moguće rezerve metode indukcije i dedukcije. Razmatrani primjeri nam omogućavaju da zaključimo da površna i nesposobna (nepromišljena, kako kažu) primjena čak i najtačnijih i najpouzdanijih metoda uvijek dovodi do pogrešnih rezultata.

U masovnoj svijesti metoda dedukcije se povezuje sa slavnim Sherlockom Holmesom, koji u svojim logičkim konstrukcijama češće koristi primjere indukcije, koristeći dedukciju u pravim situacijama.

U članku se razmatraju primjeri primjene ovih metoda u različitim naukama i sferama ljudske djelatnosti.

Predavanje 6. Metoda matematičke indukcije.

Nova saznanja u nauci i životu stiču se na različite načine, ali se sva (ako ne ulazimo u detalje) dijele na dvije vrste - prijelaz iz opšteg u specifično i iz specifičnog u opšte. Prvi je dedukcija, drugi je indukcija. Deduktivno zaključivanje je ono što se obično naziva u matematici. logičko rezonovanje, au matematičkoj nauci dedukcija je jedina legitimna metoda istraživanja. Pravila logičkog zaključivanja formulisao je prije dva i po milenijuma starogrčki naučnik Aristotel. Napravio je kompletnu listu najjednostavnijih ispravnih rasuđivanja, silogizmi– „građevinski blokovi“ logike, a istovremeno ukazuju na tipično rezonovanje koje je veoma slično ispravnom, ali netačno (često se susrećemo sa takvim „pseudološkim“ rezonovanjem u medijima).

Indukcija (indukcija - na latinskom vođenje) jasno ilustruje poznata legenda o tome kako je Isak Njutn formulisao zakon univerzalne gravitacije nakon što mu je jabuka pala na glavu. Još jedan primjer iz fizike: u fenomenu kao što je elektromagnetna indukcija, električno polje stvara, "inducira" magnetno polje. „Njutnova jabuka“ je tipičan primer situacije u kojoj jedan ili više posebnih slučajeva, tj. zapažanja, “predlažu” opštu izjavu; opšti zaključak se izvodi na osnovu konkretnih slučajeva. Induktivna metoda je glavna za dobijanje opštih obrazaca kako u prirodnim tako iu ljudskim naukama. Ali ima vrlo značajan nedostatak: na osnovu konkretnih primjera može se izvući netačan zaključak. Hipoteze koje proizilaze iz privatnih zapažanja nisu uvijek tačne. Razmotrimo primjer zbog Eulera.

Izračunat ćemo vrijednost trinoma za neke prve vrijednosti n:

Imajte na umu da su brojevi dobijeni kao rezultat proračuna prosti. I to se može direktno provjeriti za svaki n 1 do 39 polinomska vrijednost
je prost broj. Međutim, kada n=40 dobijamo broj 1681=41 2, koji nije prost. Dakle, hipoteza koja bi ovdje mogla nastati, odnosno hipoteza da za svaku n broj
je jednostavno, ispostavilo se da je lažno.

Lajbnic je u 17. veku dokazao da za svaku pozitivnu celinu n broj
djeljivo sa 3, broj
djeljivo sa 5 itd. Na osnovu ovoga, pretpostavio je da je za bilo koji nepar k i bilo koje prirodne n broj
podijeljena k, ali ubrzo sam to primijetio
nije djeljiva sa 9.

Razmatrani primjeri nam omogućavaju da izvučemo važan zaključak: izjava može biti poštena u nizu posebnih slučajeva i istovremeno nepravedna općenito. Pitanje valjanosti iskaza u opštem slučaju može se rešiti upotrebom posebne metode rezonovanja tzv matematičkom indukcijom(potpuna indukcija, savršena indukcija).

6.1. Princip matematičke indukcije.

♦ Metoda matematičke indukcije se zasniva na princip matematičke indukcije , što je kako slijedi:

1) proverava se valjanost ove izjaven=1 (osnova indukcije) ,

2) valjanost ove izjave se pretpostavlja zan= k, Gdjek– proizvoljan prirodan broj 1(pretpostavka indukcije) , a uzimajući u obzir ovu pretpostavku, njegova valjanost se utvrđuje zan= k+1.

Dokaz. Pretpostavimo suprotno, odnosno pretpostavimo da izjava nije tačna za svako prirodno n. Onda postoji tako prirodno m, Šta:

1) izjava za n=m nije fer,

2) za sve n, manji m, izjava je tačna (drugim riječima, m je prvi prirodan broj za koji tvrdnja nije tačna).

Očigledno je da m>1, jer Za n=1 izjava je tačna (uslov 1). dakle,
- prirodni broj. Ispada da je to za prirodan broj
tvrdnja je tačna, a za sljedeći prirodni broj m to je nepravedno. Ovo je u suprotnosti sa uslovom 2. ■

Imajte na umu da je u dokazu korišten aksiom da bilo koji skup prirodnih brojeva sadrži najmanji broj.

Dokaz zasnovan na principu matematičke indukcije naziva se metodom potpune matematičke indukcije .

 Primjer6.1. Dokažite to za bilo koji prirodni n broj
djeljivo sa 3.

Rješenje.

1) Kada n=1, dakle a 1 je djeljiv sa 3 i tvrdnja je tačna kada n=1.

2) Pretpostavimo da je izjava tačna za n=k,
, odnosno taj broj
je djeljiv sa 3, a mi utvrđujemo da kada n=k+1 broj je djeljiv sa 3.

Zaista,

Jer Svaki član je djeljiv sa 3, tada je i njihov zbir djeljiv sa 3. ■ 

 Primjer6.2. Dokaži da je zbir prvog n prirodni neparni brojevi jednak je kvadratu njihovog broja, tj.

Rješenje. Koristimo metodu potpune matematičke indukcije.

1) Provjeravamo valjanost ove izjave kada n=1: 1=1 2 – to je tačno.

2) Pretpostavimo da je zbir prvog k (
) neparnih brojeva jednak je kvadratu broja tih brojeva, tj. Na osnovu ove jednakosti utvrđujemo da je zbir prvog k+1 neparni brojevi je jednako
, to je .

Koristimo našu pretpostavku i dobijamo

. ■ 

Za dokazivanje nekih nejednakosti koristi se metoda potpune matematičke indukcije. Dokažimo Bernoullijevu nejednakost.

 Primjer6.3. Dokaži to kada
i bilo koje prirodne n nejednakost je tačna
(Bernoullijeva nejednakost).

Rješenje. 1) Kada n=1 dobijamo
, što je tačno.

2) Pretpostavljamo da kada n=k postoji nejednakost
(*). Koristeći ovu pretpostavku, to dokazujemo
. Imajte na umu da kada
ova nejednakost vrijedi i stoga je dovoljno razmotriti slučaj
.

Pomnožimo obje strane nejednakosti (*) brojem
i dobijamo:

To je (1+
.■ 

Dokaz metodom nepotpuna matematička indukcija neke izjave u zavisnosti od n, Gdje
izvedeno na sličan način, ali se na početku uspostavlja pravičnost za najmanju vrijednost n.

Neki problemi ne navode eksplicitno tvrdnju koja se može dokazati matematičkom indukcijom. U takvim slučajevima morate sami uspostaviti obrazac i postaviti hipotezu o valjanosti ovog uzorka, a zatim koristiti metodu matematičke indukcije da testirate predloženu hipotezu.

 Primjer6.4. Pronađite iznos
.

Rješenje. Nađimo sume S 1 , S 2 , S 3. Imamo
,
,
. Pretpostavljamo da za bilo koji prirodni n formula je važeća
. Da bismo provjerili ovu hipotezu, koristit ćemo metodu potpune matematičke indukcije.

1) Kada n=1 hipoteza je tačna, jer
.

2) Pretpostavimo da je hipoteza tačna za n=k,
, to je
. Koristeći ovu formulu, utvrđujemo da je hipoteza istinita čak i kada n=k+1, tj

Zaista,

Dakle, na osnovu pretpostavke da je hipoteza tačna kada n=k,
, dokazano je da to vrijedi i za n=k+1, a na osnovu principa matematičke indukcije zaključujemo da formula vrijedi za bilo koji prirodan broj n. ■ 

 Primjer6.5. U matematici je dokazano da je zbir dvije ravnomjerno neprekidne funkcije uniformno kontinuirana funkcija. Na osnovu ove izjave, morate dokazati da je zbir bilo kojeg broja
uniformno kontinuiranih funkcija je uniformno kontinuirana funkcija. Ali pošto još nismo uveli koncept „jednoliko kontinuirane funkcije“, postavimo problem apstraktnije: neka bude poznato da je zbroj dviju funkcija koje imaju neko svojstvo S, sama ima imovinu S. Dokažimo da zbir bilo kojeg broja funkcija ima svojstvo S.

Rješenje. Osnova indukcije ovdje je sadržana u formulaciji samog problema. Nakon što ste napravili indukcijsku pretpostavku, razmotrite
funkcije f 1 , f 2 , …, f n , f n+1 koji imaju svojstvo S. Onda . Na desnoj strani, prvi pojam ima svojstvo S po hipotezi indukcije, drugi član ima svojstvo S po stanju. Prema tome, njihov zbir ima svojstvo S– za dva mandata osnova indukcije „radi“.

Ovo dokazuje tvrdnju i mi ćemo je dalje koristiti. ■ 

 Primjer6.6. Pronađite sve prirodno n, za koje je tačna nejednakost

.

Rješenje. Hajde da razmotrimo n=1, 2, 3, 4, 5, 6. Imamo: 2 1 >1 2, 2 2 =2 2, 2 3<3 2 , 2 4 =4 2 , 2 5 >5 2, 2 6 >6 2. Dakle, možemo postaviti hipotezu: nejednakost
ima mjesta za svakoga
. Da bismo dokazali istinitost ove hipoteze, koristit ćemo princip nepotpune matematičke indukcije.

1) Kao što je gore utvrđeno, ova hipoteza je tačna kada n=5.

2) Pretpostavimo da je tačno za n=k,
, odnosno nejednakost je tačna
. Koristeći ovu pretpostavku, dokazujemo da je nejednakost
.

Jer
i at
postoji nejednakost

at
,

onda to dobijamo
. Dakle, istinitost hipoteze na n=k+1 proizlazi iz pretpostavke da je tačno kada n=k,
.

Iz paragrafa. 1 i 2, na osnovu principa nepotpune matematičke indukcije, slijedi da je nejednakost
istina za svako prirodno
. ■ 

 Primjer6.7. Dokažite to za bilo koji prirodan broj n formula diferencijacije je važeća
.

Rješenje. At n=1 ova formula izgleda
, ili 1=1, odnosno tačno je. Uz indukcijsku pretpostavku, imamo:

Q.E.D. ■ 

 Primjer6.8. Dokazati da je skup koji se sastoji od n elemenata, ima podskupovi

Rješenje. Skup koji se sastoji od jednog elementa A, ima dva podskupa. Ovo je tačno jer su svi njegovi podskupovi prazan skup i sam prazan skup, i 2 1 =2.

Pretpostavimo da je svaki skup od n elemenata ima podskupovi Ako se skup A sastoji od n+1 elemenata, onda u njega fiksiramo jedan element - označavamo ga d, i podijeliti sve podskupove u dvije klase - one koje ne sadrže d i koji sadrži d. Svi podskupovi iz prve klase su podskupovi skupa B koji se dobija od A uklanjanjem elementa d.

Skup B se sastoji od n elemenata, pa prema tome, indukcijom, ima podskupovi, dakle u prvoj klasi podskupovi

Ali u drugoj klasi postoji isti broj podskupova: svaki od njih se dobija iz tačno jednog podskupa prve klase dodavanjem elementa d. Dakle, ukupno skup A
podskupovi

Time je izjava dokazana. Imajte na umu da to vrijedi i za skup koji se sastoji od 0 elemenata - prazan skup: on ima jedan podskup - sebe i 2 0 = 1. ■ 