Matematička Indukcija II dio


Nastavak prethodnog posta o matematičkoj indukciji…..  Cjelokupan tekst može se pogledati ovdje.

Zadatak 2: Dokazati da za svaki prirodan broj n vrijedi:

clip_image002

dijeljivo sa 7.

Dokaz: Prvi korak napravimo na brzinu jer jedino je to ovdje shvatljivo.

Za n=1, clip_image004 , djeljivo sa 7

Za n=2, clip_image006, djeljivo sa 7.

Pretpostavimo da je Zadatak 2, za neki prirodan broj n=k (k>n0) dijeljiv sa 7. To znači slično kao i u primjeru da možemo pisati:

clip_image008 —–(13)

Treći korak sprovodimo kao u primjeru 2:

clip_image010

Vidimo da je izraz u zagradi ona ista pretpostavka sa pročetka primjera jednačina (13), pa je ona dijeljiva sa 7, a broj 35 je svakako dijeljiv sa 7 pa cijeli izraz je dijeljiv sa 7.

clip_image012

Vidimo da iz pretpostavke za n=k, broj clip_image014 djeljiv sa 7, dokazali smo da je za n=k+1 takodjer djeljivo sa 7 to znači da je izraz djeljiv za 7 za svaki prirodan broj.

Vidljivo je da smo dokazali neke primjere i zadatke pomoću matematičke indukcije dosta jednostavno. Međutim ostali zadaci koji dati nisu ništa zahtjevniji od ovih. Jedino je problem u tome što idući zadaci zahtijevaju malo više poznavanja elementarne matematike. To je ona matematika koju ste radili u Osnovnoj i srednjoj školi. Znači bez straha i bilo kakvih averzija okrenite siljedeći list i naići ćete na najljepši zadataka u matematičkoj indukciji. Sljedeći zadatak je bio MISS Ljeta 1888 godine, njegove prve i druge pratilje slijede iza njega.

Zadatak 3: Dokazati da vrijedi za svaki prirodan broj:

clip_image016

Rješenje:

Za n=1,

clip_image018

tačno.

Za n=2,

clip_image020

tačno.

Pretpostavimo da zadatak 3 vrijedi za n=k, odnosno:

clip_image022

Poznato vam je da uvijek kod ovakvih zadataka u trećem koraku uvijek dodajemo objema stranama sljedeći broj zadnjeg broja lijeve strane. S toga imamo:

clip_image024

clip_image026

clip_image028

clip_image030

clip_image032

U zadatku 1 smo diskutovali o sljedećem broju nepranih brojeva. Sljedeći broj broja 2k+1 je 2k+3, jer je 2(k+1)+1= 2k+3. Zadnja jednakost (16) znači da smo iz pretpostavke (15) vrijedni za n=k, dokazali da vrijedi i za n= k+1, pa zaključujemo po matematičkoj indukciji da Zadataka 3 vrijedni za sve prirodne brojeve.

Do jednakosti (13) iz jednakosti (12) lako smo došli iako se nekima čini da nije. Ove sve k-ove koje vidite u zadnjim jednakostima, to je u stvari samo jedan k, ali napisan u drugim oblicima.

Ako bolje pogledate sve one transformacije vidjećete da se one sastoje samo u sabiranju razlomaka, izvlačenju zajedničkih množitelja i nekoliko dvica, trica i šestica.

Zadatak 4: Dokazati da vrijedi za svaki prirodan broj:

clip_image034

Rješenje:

Za n=1,

clip_image036

tačno.

Za n=2,

clip_image038

tačno.

Pretpostavimo da zadatak 4 vrijedi za neki prirodan broj k, odnosno:

clip_image040

Korak 3 koji slijedi sličan je kao i u zadatku 3, tj. dodajmo objema stranama clip_image042 pa imamo:

clip_image044

clip_image046

clip_image048

Vidimo da uz prepostavku za n=k, izraz vrijedi i za n=k+1, s toga i za svaki prirodan broj.

Zadatak 5: Dokazati da vrijedi za svaki prirodan broj:

clip_image050

Rješenje:

Za n=1,

clip_image052

tačno.

Za n=2,

clip_image054

tačno.

Pretpostavimo da jednakost vrijedi za neki n=k,tj.

clip_image056

Sada kada smo napisali pretpostavku po ko zna koji put moramo dodati sljedeći broj broja k(k+1), a to je (k+1)(k+2), pa imamo:

clip_image058

clip_image060

clip_image062

Vidimo da smo iz pretpostavke da vrijedi za n=k, dokazali da zadnja jednakost vrijedi i za n=k+1, što znači da vrijedi i za svaki prirodan broj n.

Zadatak 6: Dokazati da je za svaki prirodan broj, broj:

clip_image064

djeljivo sa 9.

Rješenje:

Za n=1,

clip_image066

dijeljivo sa 9.

Za n=2,

clip_image068

dijeljivo sa 9.

Pretpostavimo da je za n=k, izraz (15) dijeljiv sa 9. To možemo pisati kao:

clip_image070

Za n=k+1, imamo:

clip_image072

clip_image074

clip_image076

Ponovo vidimo da koristeći pretpostavku lako dokazujemo da nam izraz (15) dijeljiv sa 9, za svaki prirodan broj. Sve to nam omogućuje matematička indukcija. Bez nje ne bismo lako dokazali ne samo ovaj zadatak. Zato s pravom moramo reći: Hvala ti hvala draga naša indukcijo.

Zadatak 7: Dokazati da za svaki prirodan broj broj:

clip_image078

dijeljiv sa 10.

Dokaz:

Za n=1,

clip_image080

dijeljivo sa 10.

Za n=2,

clip_image082

dijeljivo sa 10.

Pretpostavimo da je za n=k, izraz (16) dijeljiv sa 10. To možemo pisati kao:

clip_image084

Za n=k+1, imamo:

clip_image086

clip_image088

Vidimo da iz prtpostavke za n=k lako dokazujemo da (16) vrijedi za n=k+1, odnosno da vrijedi za svaki prirodan broj.

Zadatak 8: Dokazati da za svaki prirodan broj broj:

clip_image090

dijeljiv sa 5.

Dokaz:

Za n=1,

clip_image092

dijeljivo sa 5.

Za n=2,

clip_image094

dijeljivo sa 5.

Pretpostavimo da je za n=k, izraz (18) dijeljiv sa 5. To možemo pisati kao:


clip_image096

Za n=k+1 imamo:

clip_image098

clip_image100

Jednostavnim dokazom, uz pomoć pretpostavke, dokazali smo da izraz (18) vrijedi za k=k+1, pa nam zbog matematičke indukcije v ijedi za svaki prirodan broj. Glavni šablon ovog tipa zadataka (o djeljivosti ) je da kada se radi treći korak u eksponentu ostavi onoliko koliko ima u pretpostavci, a višak se spusti kao množitelj. Taj množitelj izvlačimo ispred zagrade dok u zagradi stavljamo samo ono što je u pretpostavci. Dakle mi se bi „naštimamo“ pretpostavku a sve ono što moramo oduzeti ili dokazati stavljamo iza zagrade. Nije slučajno da sav višak uvijek bude djeljiv sa onim brojm za kojeg ga mi provjeravamo.

Treći česti slučaj tipova zadataka koji se dokazuju matematičkom indukcijom su nejednakosti. One su još jednostavnije, a sve se bazira na tome da ako je npr. 150 > 50, tada je i 200>50, odnosno 150 >1.

Prije nego to pređemo na zadatke uvedimo pojam Leme.

Lema je pomoćna teorema. Odnosno to je jedan mali podzadatak nekog zadatka. Ako rješavamo neki zadatak i dođemo do jedne tvrdnje koju moramo posebno dokazivati mi je definišemo kao lemu.

Zadatak 9: Dokazati da za svaki prirodan broj n,gdje je clip_image102 vrijedi nejednakost:

clip_image104

Dokaz: Pošto ovaj zadatak dokazujemo pomoću matematičke indukcije onda se moramo držati njenih postavki i redoslijeda. Što znači da prvo moramo provjeriti da li ta nejednakost vrijedi za prvih nekoliko prirodnih brojeva. Uslov zadatka na kaže da provjerimo od 5 pa dalje.

Za n=5,

clip_image106

clip_image108

Nejednakost je tačna.

Za n=6,

clip_image110

clip_image112

Nejednakost je tačna.

Dokažimo Lemu koja kaže:

Lema 1: Za svaki m>2 izraz clip_image114

Dokaz:

Ovu lemu također ćemo dokazati matematičkom indukcijom.

Za n=3,

clip_image116

clip_image118

Tvrdnja je tačna.

Za n=4,

clip_image120

clip_image122

Tvrdnja je tačna.

Neka je za neki m=l (l>2) vrijedi:

clip_image124

Za m=l+1 imamo:

clip_image126

clip_image128

clip_image128[1]

clip_image130

clip_image132

Zadnja nejednakost koju smo dobili je očigledna. Jer je l>2 pa svaki kvadrat je većiod dva.

AKosada tu trivijalnu nejednakost stavimo kao prvu i krenemo unazada doći ćemo do nekednakosti (21), što znači da je nejednakost tačna. Znači po principu matematičke indukcije Lema 1 je tačna za sve prirodne brojeve veće od 2.

Lemu 1 možemo koristiti kao dokazni materijal u sve i jednom sadašnjem i budućem zadatku.

Nastavimo rješavanje zadatka 9. Ostao nam je treči korak pa sada imamo:

Za n=k+1 imamo:

clip_image134

clip_image136

Maloprije smo dokazali da nam je:

clip_image138

Ako sada lijevoj i desnoj strani (Leme 1) dodamo broj clip_image140imamo:

clip_image142

Sada stupa na scenu naša pretpostavka (kada je pomnožimosa 2) koja kaže da je:

clip_image144

Pomnožimo je sa 2 imamo:

clip_image146

Pa je:

clip_image148

odnosno,

clip_image134[1]

Vidimo das mo i ne znajući dokazali da je iz pretpostavke za n=k nejednakost vrijedi za n=k+1, što nam je potrebno I dovoljno da kažemo da nejednakost vrijedi za svaki prirodan broj.

Ako neko čitajući ovo rješenje zadatka 9, nije shvatio posljednje nejednakosti, predlažem da pročita mali uvod o dokazivanju nejednakosti I obrati pažnju na činjenicu da ako je npr: 150>50 tada je 200>50 odnosno 150 >1.

Zadatak 10: Dokazati da za svaki prirodan broj veći ili jednak od 5 vrijedi nejednakost:

clip_image150

Rješenje:

Za n=5,

clip_image152

clip_image108[1]

Nejednakost je tačna.

Za n=6,

clip_image154

clip_image156

Nejednakost je tačna.

Pretpostavimo da je za neki n=k , clip_image158 vrijedi:

clip_image160

Koristeći ovu pretpostavku (22), te koristeći nejednakost da je clip_image162, što je očigledno jer je: clip_image164, dobijamo treći korak odnosno dokaza ćemo treći korak a samim tim i zadatak 11.

Dakle,

clip_image166

clip_image168

Sabiranjem gornjih nejednakosti imamo:

clip_image170

Odnosno sređivanjem:

clip_image172

Zadnjim izrazom da nejednakost vrijedi i za n= k+1. Zadnje nejednakosti daju nam zaključiti ako imamo na umu matematičku indukciju da izraz (22) vrijedi za svaki prirodan brojclip_image174

Zadatak 11: Dokazati da za svaki prirodan broj clip_image176 vrijedi nejednakost:

clip_image178

Rješenje:

Za n=2 imamo:

clip_image180

Za prvi prirodan broj za koji treba dokazati da vrijedi nejednakost (23) imamo izraz (24). Kod deduktivnog načina dokazivanja nejednakosti (kojeg ćemo sada primjeniti) trebamoiz polazne nejednakosti (24) nizom matematičkih dozvoljenih operacija doći do trivijalne nejednakosti koju lako primjećujemo čak i kad te brojeve zamijenimo sa kruškama i jabukama.

Pokušajmo to sa nejednakosti (24):

clip_image182

Sabiranjem lijeve strane:

clip_image184

Pomnožimo cijelu nejednakost sa clip_image186.

clip_image188

Odnosno:

clip_image190

Sada smodošli do jedne trivijalno-očigledne nejednakosti, gdje u svaka doba dana i noći znamo daje clip_image192, što znači da je izraz (23) tačan za n=2.

Za n=3 imamo:

clip_image194

Istim postupkom kao i za n=2 imamo:

clip_image196

Sabiranjem lijeve strane:

clip_image198

Množenjem sa clip_image200 imamo:

clip_image202

clip_image204

clip_image206

Kvadriranjem cijele nejednačine:

clip_image208

clip_image210

clip_image212

U svako doba dana i noći mi znamo da nam je clip_image214 pozitivno i uvijek veće od bilo kojeg negativnog broja, što znači da je izraz (25) tačan.

Pretpostavimo da je za neki n=k izraz (23) tačan, tj:

clip_image216

Na tako pretpostavljenu nejednakost dodajmo k+1.-vi član. Imamo:

clip_image218

Dokažimo sada da je:

clip_image220

Ostavljanjem samo clip_image222 na lijevoj strani a ostatak prebacimo na desnu imamo:

clip_image224

Pa je:

clip_image226

Množenjem sa clip_image228 imamo:

clip_image230

Kvadriranjem cijele nejednakosti imamo:

clip_image232

Odnosno:

clip_image234

Odnosno:

clip_image236

Što vrijedi za svaki prirodan broj pa i polazna nejednakost. Ako sada ovu dokazanu nejednakost primjenimo na (27) imamo:

clip_image238

Odnosno

clip_image240

Pa zaključujemo da smo preko pretpostavke (26) došli do zaključka da (23) vrijedi za svaki prirodan broj.

Vidjeli smo kako se rješavaju nejednačine preko matematičke indukcije. U biti sve se svodi na pomenutu nejednakost akoje 150>50 tada je i200>50 tj. 150>1.

About Bahrudin Hrnjica

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

Posted on 05/06/2010, in Math and tagged . Bookmark the permalink. 11 Comments.

  1. extra

  2. Wow, this article is good, my younger sister is analyzing these things, thus I am going to tell her.

  3. Hi there I am so excited I found your webpage, Ireally found you by accident, whhile I was
    researching on Bing for something else, Nonetheless
    I am here now and would just like to say thank you for a
    incredible post and a all round enjoyable blog (I alseo lovve
    the theme/design), I don’t hzve time to read though it all at
    the minute but I have saved it and also added in yur RSS feeds, so when I ave time I will be back to
    read much more, Please do keep up the awesome jo.

  4. The professionals should not seo just about as well.
    If you’ve got a great impact on the website at thundertech.

  5. If you want to do is draw a box at the cost you a bit about LifeListed.

    These free infographic designing tools like paper and search
    engine optimization try to keep in mind is, therefore when embarking
    on this via your provider. Custom web pages Dynamic web pages instead of hauling around the world is an extra
    demand right now that are successful. These two,
    Visual Design courses include: Illustration for the website.
    For starters, no matter what form, but not Firefox.

  6. Depending on the Paths tab, lead generation right there.
    It prevents the escalation of costs are relatively
    easy task to select someone who creates wire frames of a faith, thereby securing transactions.
    But it does certainly pays off in the field of expertise.
    While business owners forget! Most of your site with images with explicitly specified width and height, etc.

  7. Appreciating the hard work you put into your site and in depth information you present.
    It’s nice to come across a blog every once in a while that isn’t the
    same out of date rehashed information. Great read!
    I’ve saved your site and I’m including your RSS feeds to my Google account.

  8. It ranks up there with the likes of getting to meet Johnny Depp, the best dessert you
    ever ate, and your husband doing all laundry and cooking
    for an entire month. Google+ is a social networking site
    that has a range of different features that you can use to connect with patients and other healthcare professionals.
    how can businesses effectively use this new
    social media platform.

  9. portal www

    Good information. Lucky me I ran across your blog by accident (stumbleupon).
    I’ve book marked it for later!

  10. What ɑ data of un-ambiguity аnd preserveness οf precious
    ƙnow-how гegarding unexpected emotions.

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