Matematička Indukcija


…dio teksta napisanog 1996 o nekim temama iz matematike…. Cjelokupan tekst može se pogledati ovdje.

Uvodne riječi

Inspirisan skromnim iskustvom u prenošenju znanja mojim prijateljima i kolegama na fakultetu, odlučio sam da pokušam napisati ovaj tekst, u kojem sam obradio na nestandardan način neke teme iz područja matematike, koje se studiraju na prvoj godini Mašinskog fakulteta u Bihaću. Gotovo sve knjige iz matematike tako strogo obrađuju teme kao što i sama matematika to zahtjeva. Pokušao sam sebi dati malo slobode da na jedan nestandardan način potenciram i obradim neke detalje koji površno gledajući ne zahtijevaju mnogo pažnje, a temelj su u stvaranju prave slike i rasuđivanja u matematici.

Mnogi studenti dobijaju komplekse i razne male „traume“ kada ugledaju te silne teoreme, te matematičke simbole i zadatke. Koristio sam jedan, više simbolički način u rješavanju zadataka, a ne odstupajući od standarda rješavanja. Na taj način želio sam približiti i dati više hrabrosti studentima da se upuste u proučavanje te tako neophodne grane nauke i objasniti sve te strogo definisane zakone kroz jednu vrstu humora sa puno simbolike a koji u biti ostaju tamo gdje su uvijek pripadali – u matematici.

Protekli rat je učinio da mnogi studenti koji pohađaju I godinu nisu dolazili u dodir sa mnogim stvarima iz matematike, koje se obrađuju u srednjim školama. Kada jedan takav ratni srednjoškolac počinje da susreće sve te maloprije navedene stvari pada u jednu vrstu averzije prema matematici bez koje nikako ne može da napreduje. Averzija i strah od matematike u studentu živi cijelo vrijeme i jednostavno ga koči. U takvom stanju student postaje fobičan na svaku novu informaciju. On tada traži druge putove spoznaje: drži se strogih šablona uči na pamet određene teoreme i formule, jednostavno vodi jednu ogorčenu bitku s matematikom.

Prije nego što počnete čitati prve stranice ovog teksta, neka mi ne zamjere svi oni koji smatraju ovo nečim što ne pripada ovoj temi. Moj jedini cilj je u tome da ovaj djelić matematike bude lakše shvatljiv svim onima koji zbog rata to nisu dobili.

Bahrudin Hrnjica
U Bihaću, decembra 1996. godine.

Neki studenti i srednjoškolci, pri prvom susretu sa matematičkom indukcijom dobiju nekakav, nazvao bi ga »induktivni otpor« u moždanoj zavojnici. Radi smanjivanja i potpunog uklanjanja induktivnog otpora predlažem vam slijedeće.

» Zaboravite sve što ste znali, do sada, o Principu matematičke indukcije!«.

Kada ste obrisali i uklonili sve moždane vijuge glede matematičke indukcije, uvest ću vas u nju jednim drugim u biti istim putem. Prije nego što krenem u tu čudesnu i nevjerojatnu stvarnost ispičaću vam priču tko je kriv za to što nemate sna, i za sve noćne more koje dobijate od matematičke indukcije.

Sve je počelo ne tako davno, negdje blizu 20-tog stoljeća, kada je L. Peano ljetovao oko Venecije. U to doba dosta se govorilo o brojevima, posebno na gradskim trgovima i pijacama. Ali Peana, kao matematčara, nije zanimalo koliko šta košta, nego nešto sasvim drugo. On je razmišljao o tome kako sve te brojeve, koji su tako često u razgovoru i upotrebi, definiše i zasnuje na matematičkim osnovama, odnosno kako brojeve definisati pomoću jednog zatvorenog neproturječnog i konačnog skupa aksioma.

Jednog dana tako je i bilo…

Definicija 1 : Skupom Prirodnih bojeva zovemo svakim skupom N za čija ma koja dva elementa clip_image002 i clip_image004 postoji odnos da clip_image004[1] slijedi poslije clip_image002[1], i koji zadovoljavaju slijedeće aksiome.

Aksioma 1: 1 je prirodan broj.

( To je revolucionarno otkriće koje je mali korak za ljude sa trga a veliki za Peana)

Aksioma 2: Svaki prirodan broj clip_image002[2] ima svoj slijedeći broj clip_image004[2].

(Također ništa veći korak od prvog)

Aksioma 3: clip_image006. (Ili, jedan nije slijedeći broj ni za koji prirodan broj)

Aksiom 4: clip_image008. Dva prirodna broja su jednaka ako su im jednaki njihovi sljedeći brojevi.

Napomena

Ova aksioma proizašla je nakon napornog rada na njivi gdje je Peano brao tek sazrjeli limun. »I limun je žut zar ne«.

Peta Peanova aksioma-aksioma poznata je pod nazivom »Noćna mora«. Aksioma zbog koje vi ne spavate, ne jedete, aksioma koja je frustrirala najviše studenata od svih Peanovih aksioma. Njen treći naziv je u narodu poznat pod imenom AKSIOMA INDUKCIJE.

Aksioma 5: Ako neki skup M prirodnih brojeva ima svojstvo:

· 1ϵM

· ako postoji prirodan brojclip_image010, pa također i njegov clip_image012. Tada M sadrži sve prirodne brojeve tj. M je identičan sa skupom prirodnih brojeva.

Nešto nije jasno? Da to je Aksioma indukcije. Šta, buni vas to što se spominju nekakvi skupovi M i N. Pa lijepo sam vam rekao da zaboravite sve što ste znali o matematičkoj indukciji.

Zadnja Peanova aksioma definiše matematićku indukciju.

Možda vam sad ništa nije jasno, ni matematička indukcija ni peanovi aksiomi. Možda vam je jedino jasno zašto je limun žut.

Tako sve počelo ( mislim na noćne more i branje limuna)…

To je bio čovjek koji je za sve kriv tj. definisao je matematičku indukciju. Reći ću vam nešto u povjerenju: Tu priču sam i ja čuo. Meni je bilo lakše, a vama…..?

Peta Peanova aksioma ili Aksioma indukcije modificirana je u teoremu. No prije nego je izložim pročitajte slijedeći primjer.

Zamislite da ste u vinskom podrumu i morate provjeriti kvalitet u 10 000 buradi. Jedino sto vlasnik želi od vas jeste da ga trijezni izvjestite da li je vino u svim buradima istog kvaliteta u roku od 15 minuta.

Sada kada je pred vama jedan gotovo nerješiv problem, ne klonite duhom. S takvim i sličnim situacijama priskače u pomoć ‘noćna mora’, hoću reći matematička indukcija.

Način na koji bi riješili ovakav problem sastoji se u sljedećem.

Probajte prvih nekoliko buradi s vinom. Uvjerite se da je vino istog kvaliteta. Sada ‘uzmite’ nasumice izabrano bure i pretpostavite da je vino zadanog kvaliteta (možete te ga čak i probati). Tada ispitajte vino u sljedećem buretu. Ako je ocjena ista kao kod pretpostavljenog bureta, možete otići vlasniku i obavijestiti ga da ste riješili problem odnosno da je vino istog kvaliteta.

Vlasnik će vam povjerovati jer poznaje princip matematičke indukcija.

Napomena

Ni u kom slučaju nemojte popiti previše vina.«.

Ovo ne morate čitati

U matematici postoje dva načina rasuđivanja:

Deduktivno

Induktivno

Deduktivni način rasuđivanja vodi do toga da morate probati vino u svim buradima i onda tako pijani date izvještaj vlasniku o kvalitetu vina u buradima. Drugim riječima dedukcija je način rasuđivanja u matematici koji se bazira na tome da sve pojedine zaključke dobijamo iz jednog općeg zakona.

Induktivni način zaključivanja, koji smo već prezentirali u primjeru, vodi do toga da pojedinačnim zaključivanjema dolazimo do jednog općeg zaključka.

Ako se sada svo to vino i burad zamijeni sa prirodnim brojevima dobijamo: princip matematičke indukcije.

Definicija 2 : PRINCIPA MATEMATIČKE INDUKCIJE. Ako neka tvrdnja P(n), koja zavisi od prirodnog broja n, vrijedi za prvih nekoliko prirodnih brojeva, te ako iz pretpostavke, da vrijedi za neki prirodni broj n=k tvrdnja P(k) vrijedi i za n=k+1, pomenuta tvrdnja vrijedi za sve prirodne brojeve odnosno za svaki prirodan broj n.

Za početak riješi ćemo jedan primjer. Sljedeći primjer je najjednostavniji primjer koji se rješava pomoću matematičke indukcije. Doista, jednostavnijeg primjera nema. Primjer je toliko jednostavan da ga ne možemo zvati zadatak.

Primjer 1 : Potrebno je provjeriti da li:

clip_image014

vrijedi za sve prirodne brojeve.

Dokaz:

Prije samog početka vratite se na definiciju matamatičke indukcije. Nakon što ste još jednom pročitali definiciju, pročitajte je još jednom , i obratite pažnju na prvi dio rečenice. Definicija teoreme kaže da svaku trvdnju, bilo ona u obliku prmjera, ili zadatka, teoreme ili vinskog podruma – potrebno je provjerili validnost tvrdnje za prvih nekoliko prirodnih brojeva.

Uzmimo da je n=1.

Sada se dešava sljedeće (pošto je n=1):

clip_image016

vidimo da, ako izračunamo desnu stranu, dobijamo:

clip_image018.

To znači da početna tvrdnja (1) vrijedi za prvi prirodan broj, što ne povlači da vrijedi ako je n=2, u to se moramo uvjeriti.

Ako je n=2, primjer se svodi na:

clip_image020

odnosno,

clip_image022

Vidimo da je tvrdnja (1) tačna i za n=2. Sada možemo preći na drugi korak jer nema smisla provjeravati dalje pojedinačno validnost trvdnje primjera 1. Međutim, ako se radi o vinskim buradima provjerava se najmanje prvih deset.

Pošto ste savladali prvi korak predlažem da pročitate ponovo definiciju matematičke indukcije i obratite pažnju na drugi dio rečenice tj. ‘ako iz pretpostavke da vrijedi na n=k …’.

Ovo znači da moramo izabrati neki prirodan broj k, znači bilo koji. Pošto je bilo koji, to ne možemo reći da je primjerice 5, 15 ili 155. Samim tim mi se nismo ograničili na određeni.

Pretpostavimo da za bilo koji n=k vrijedi tvrdnja (1). Na matematičkom jeziku zadnja rečenica izgleda sljedeće:

clip_image024

Sada pročitajte ponovo definiciju i pažnju stavite na zadnji dio rečenice ‘tvrdnja vrijedi za n=k’. To znači da moramo dokazati da tvrdnja vrijedi za n=k iz pretpostavke (2). U stvari mi sebi nešto pretpostavimo da bi smo s tom pretpostavkom nešto dokazali. To je isto kada moramo pretpostaviti da će vino poteći iz bureta prije nego natočimo čašu, inače ne bi ni otvarali bure.

Ovo je najbitniji momenat procedure dokazivanja baziranog na matematičkoj indukciji. Treći dio najjednostavnije možemo riješiti ako se pravimo da ništa ne znamo.

Napišimo pretpostavku:

clip_image026

U pretpostavku moramo uključiti sljedeći broj broja k tj. k+1 jer to definicija zahtjeva od nas. Ako sada, pošto ništa ne znamo, imamo na umu da jednoj ekvivalentnosti (bilo ona pretpostavljena ili ne) možemo dodati isti broj sa lijeve i desne strane i da ona i tada ostaje nepromijenjena (identična), tada smo primjer dokazali. Kako?

Dakle dodajmo lijevoj i desnoj strani sljedeći broj broja k. Broj koji je dodan je boldiran. Dobijamo:

clip_image028

Sada je potrebno lijevu i desnu stranu izmanipulisati tako da, gdje je god stajao broj k, mora biti sljedeći broj k+1. Jedino u takvom slučaju zadovolji ćemo definiciju 1, odnosno onog tipa iz Italije.

Pogledajmo lijevu stranu izraza (4). Tamo je k bio na posljednjem mjestu u jednakosti (2), sada stoji k+1. Znači tu smo odradili posao. Na desnoj strani imamo:

clip_image030

Postupiti ćemo kao da se nista ne dešava i uradi ćemo sve ono što se može uraditi na tako „oskudnoj“ desnoj strani. Sabraćemo razlomak sa k+1. Imamo:

clip_image032

Izvlačenjem zajedničkog člana k+1 u brojniku dobijamo sljedeće:

clip_image034

Odnosno

clip_image036

Promatrajući desnu stranu uočavamo da, gdje je god bio broj k i k+1 sada stoje sljedeći brojevi : k+1 i k+2 (odnosno (k+1)+1). A to znači da smo iz pretpostavke dokazali da tvrdnja vrijedi za n=k+1 prirodan broj.

Po posljednji put pročitajte definiciju, a pažnju usmjerite prema zadnjoj odnosno drugoj rečenici: ‘Tvrdnja vrijedi za svaki prirodan broj’.

Ako definicija kaže tako onda budite sigurni da ste stvarno dokazali primjer 1. Ako nevjerujete u to, predlažem vam da odete na pusto ostrvo sa šleperom papira i hrane, te polahko krenite od 1. Ostatak života ćete sigurno potrošiti dokazujući tvrdnju deduktivno, a možda ćete dospjeti i do naslovnica svjetskih časopisa pod naslovom ‘Čovjek sa pustog ostrva izmišlja toplu vodu’.

Ako ste shvatili prethodni primjer predlažem vam da odete u podrum i probate vino u 11-tom buretu.

Zadatak 1 : Dokazati primjenom matematičke indukcije da:

clip_image038

vrijedi za svaki prirodan broj.

Rješenje:

Čim pogledamo zadatak primjetićemo da je lijeva strana zbir prvih n neparnih brojeva (desna strana je njihova vrijednost).

Ako je n=1 dobijamo,

clip_image040, tj. clip_image018[1]

clip_image042, tj. clip_image044

Pretpostavimo da je za n=k tvrdnja 6 tačna odnosno da je:

clip_image046

Smatrajući da su prva dva koraka razumljiva problem predstavlja korak 3, odnosno da iz pretpostavke 7, dokažemo da tvrdnja vrijedi i za n=k+1, što definicija hoće „reći“, da dokažemo da tvrdnja vrijedi i tada kada ubacimo u zbir i sljedeći neparni broj od broja 2k-1, odnosno 2k+1.Lijevoj i desnoj strani dodajemo broj 2k+1.

Možda se pitate: Zašto baš 2k+1? Zašto nije neki drugi, ljepši broj?

Pa jednostavno zato što je limu žut, tj. Pošto definicija traži od nas, da stavimo u glavnu ulogu broj k+1.

Kod postavljanja u glavnu ulogu broja k+1, morate ići na to da što jeftinije prođete s tim glumcem. Hoću reći da morate biti što ljenji glede rješavanja matematičkih zadataka.

Broj 2k+1 je sljedeći broj od broja 2k-1. Evo zašto: Kada u broj 2k-1, umjesto k stavimo sljedeći broj tj. k+1 imamo:

clip_image048

Pretpostavimo:

clip_image050

Prije nekoliko godina, vjerojatno kroz neku maglu prisjećate se 8 razreda kada vam je nastavnik govorio da je:

clip_image052

Zbog tog razloga desna strana jednakosti (8) poprima oblik:

clip_image054

Ponovo ista situacija kao i u primjeru. Gdje je god stajao broj k, sada stoji broj k+1. Zaključak se svodi na primjer:

Poprincipu matematičke indukcije naš zadatak 1 je dokazan.

Savjet

Kod bilo kojeg rješavanja ovakvih tipova zadataka uvijek kod trećeg koraka idemo na to da kada dodamoneki broj dodajemo uvijek sljedeći u nizu na lijevoj strani (na strani gdje je suma). Tada više posla sa lijevom stranom nemamo, samo je (lijevu stranu jednakosti) vučemo za sobom i sređujemo desnu stranu.

Vidjeli ste kako se neke sume dokazuju primjenom matematičke indukcije. Međutim, postoji mnogo tipova drugih zadataka koji se rješavaju ovom metodom.

Pokušaću vam objasniti kako se djeljivost nekog broja može dokazati ovom metodom (matematičkom indukcijom). Također ćemo krenuti od jednog primjera.

Primjer 2 : Dokazati da je:

clip_image056

dijeljivo sa 2 za svaki prirodan broj.

Dokaz:

Ako ste zaboravili definiciju (postupak) matematičke indukcije pročitajte je.

Provjeravamo tvrdnju za prvih nekoliko prirodnih brojeva:

Za n=1, clip_image058 , tj. 4 je dijeljivo sa 2, odnosno simbolički zapisano:

clip_image060.

Za n=2, clip_image062 , tj. 10 je dijeljivo sa 2, odnosno simbolički zapisano

clip_image064.

Vidimo da naš primjer vrijedi za prva dva prirodna broja.

Sad ćemo pretpostaviti da naša tvrdnja odnosno prosti primjer vrijedi za bilo koji broj k. Ako smo to učinili tada našu pretpostavku možemo napisati na matematičkom jeziku kao:

clip_image066, gdje je clip_image068

Za one kojim nije jasna zadnja jednakost neka ne čitaju sljedeći dio teksta.

Ako je neki prirodan boj Ž dijeljiv sa prirodnim brojem 2, tada je:

clip_image070, drugim riječima, to znači dakada podjelimo broj Ž sa brojem 2 dobijemo neki prirodni broj Č.

Ako zadnju jednakost pomnožimo sa 2 dobijamo:

clip_image072,

a što je isto kao kad smo napisali:

clip_image074

Pomoću pretpostavke (11), trebamo dokazati da je:

clip_image076

Ponovo kao i svaki put kada radimo 3 korak pravimo se da ništa ne znamo:

clip_image078

clip_image080

Ako niste shvatili zadnje jednakosti tada uzmite teku iz prvog razreda srednje škole i ponovite stepene, ako je niste naložili.

Vidimo da je izraz u zagradi isti kao i naša pretpostavka pa je dijeljiva sa 2, tj.

clip_image082

Zadnja jednakost nam daje za pravo da zaključimo kako je clip_image084 djeljivosa 2, a definicija da je primjer 2 tj. clip_image086 djeljiv sa 2 za svaki prirodan broj n.

Ako niste sigurni u ovaj dokaz postupate kao i u prethodnom primjeru br. 1.

Ovo ne morate čitati

Kada kažemo“vidimo da smo dokazali i za n=k+1“ to znači u bukvalnom smislu (razmišljanjem jednog prosječnog osnovca) da mi u stvari pretpostavku uzmemo, malo je prevrnemo, odjenemo je u odjeću, počešljamo je, kupimo joj nove cipele i od jedne pepeljuge postane princeza. Znači mi tu u stvari ništa ne dokazujemo u smislu dugotrajnih sudskih procesa, svjedočenja, advokata, porote i slično. Samo dodamo saberemo i izvučemo zajednički član i pretpostavka za čudo postane upravo ono što mi trebamo dobiti, a to je jednakost za n=k+1.

Čudno zar ne?

……..


Luigi Peano 1858-1918

About Bahrudin Hrnjica

PhD in Mechanical Engineering, Microsoft MVP for .NET. Likes .NET, Math, Mechanical Engineering, Evolutionary Algorithms, Blogging.

Posted on 01/02/2010, in Math and tagged , . Bookmark the permalink. 6 Comments.

  1. Gracias por compartilo

  2. But what makes Vi – Salus so different is the use of what is know as a
    capture page branding both the rep and the company at the same time.
    Sweet diet snack: sweet potato You may be watching your carbohydrate intake, but
    my experience is that healthy carbohydrates help me stick to a diet, feel better,
    think more clearly, and have the energy I need to exercise.

    It helps increase immunity to aid in fighting colds.

  3. If you want to grow your know-how simply keep
    visiting this web site and be updated with the most up-to-date gossip posed here.

  4. of course like your web-site but you need to check the spelling on several of your posts.
    Many of them are rife with spelling issues and
    I in finding it very bothersome to tell the truth on the other hand I’ll certainly come back again.

  5. Como cliente nem sempre é informado sobre as peculiaridades
    dos serviços de net designer é bom que profissional saiba alertar, convencer e negociar um preço que seja justo
    e que pague pela qualidade do trabalho realizado.

  6. If some one wants expert view regarding running a blog
    afterward i advise him/her to go to see this website, Keep up the
    pleasant work.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s