Matematička indukcija

Princip matematičke indukcije

Da bi za zvako n ∈ N važilo tvrdjenje T(n), dovoljno je pokazati:

bazu indukcije: tvrdjenje T(1)

induktivni korak: za svaki prirodan broj n ≥ 1 važi da ako je tačno tvrđenje T(n), onda je tačno i tvrdjenje T(n + 1).

Ako je potrebno dokazati da neko tvrdjenje važi za svaki ceo broj n ≥ b, onda je dovoljno pokazati da je tačno tvrdjenje T(b) i da je za svako i ≥ b tačna implikacija T(i) ⇒ T(i + 1).

Princip potpune matematičke indukcije

Da bi za zvako n ∈ N važilo tvrdjenje T(n), dovoljno je pokazati:

bazu indukcije: tvrdjenje T(1)

induktivni korak: za svaki prirodan broj n ≥ 1 važi da ako je tačno tvrđenje T(k), za svako k < n, onda je tačno i tvrdjenje T(n).

Zadaci

Zadatak 1

Koristeći princip matematičke indukcije dokazati da za svako n ∈ N važi:

     n       qⁿ⁺¹ - 1
     Σ  qⁱ = ————————
    i=0        q - 1

Zadatak 2

Koristeći princip matematičke indukcije dokazati da za svako n ∈ N važi:

    8 | 5ⁿ⁺¹ + 2 ⋅ 3ⁿ + 1

Uputstvo: Uvedimo oznaku S(i) = 5ⁱ⁺¹ + 2 · 3ⁱ + 1 i izrazimo S(n + 1) preko S(n).

Zadatak 3

Koristeći princip matematičke indukcije dokazati da važi 2ⁿ > n² za svaki ceo broj n veći od 4.

Uputstvo: Jednostavno se može pokazati da za broj 5 važi baza indukcije. Za svaki prirodan broj n ≥ 5 ako se pretpostavi da važi 2ⁿ > n², onda važi:

    2ⁿ⁺¹ = 2 · 2ⁿ = 2ⁿ + 2ⁿ >
                  > n² + n² >
                  > n² + 4n = n² + 2n + 2n >
                            > n² + 2n + 1 = (n + 1)²

pa je tačan i induktivni korak.

Zadatak 4

Koristeći princip matematičke indukcije dokazati da za svaki celi broj n > 1 važi sledeća nejednakost:

     2⋅n   1   13
      Σ    — > ——
    i=n+1  i   24

Zadatak 5

Dato je n ≥ 3 pravih u ravni u opštem položaju (nikoje dve nisu paralelne, a nikoje tri se ne seku u istoj tački). Dokazati da je bar jedna od oblasti koje one formiraju - trougao.

Uputstvo: Jednostavno se dokazuje da tvrdjenje važi za 3 prave.

Pretpostavimo da tvrdjenje važi za neku vrednost n ≥ 3 i pokažimo da važi i za n + 1.

Pošto su prave u opštem položaju na proizvoljan način izdvojimo jednu i posmatramo preostalih n pravih. Po induktivnoj hipotezi jedna od oblasti koju te prave formiraju je trougao.

Izdvojena prava može da nema zajedničkih tačaka sa tim trouglom (u tom slučaju je isti trougao rešenje i za n + 1 tačku) ili može da seče trougao. Ako ga seče, prava ne može imati nijednu zajedničku tačku sa njegovim temenima jer bismo u suprotnom imali tri prave koje se seku u istoj tački.

Sledi da ta prava seče ovaj trougao i jedna od oblasti na koju je seče jeste trougao.

Zadatak 6

Dat je niz 1, 2, 3, 4, 5, 10, 20, 40, … koji počinje kao aritmetička progresija, a posle prvih pet članova postaje geometrijska progresija. Dokazati da se svaki prirodan broj može predstaviti u obliku zbira različitih brojeva iz ovog niza.

Uputstvo: Preformulišimo tvrdjenje na sledeći način: dokazati da se brojevi manji od 5 · 2ⁿ, n ≥ 0 mogu predstaviti u obliku zbira različitih brojeva iz ovog niza.

Bazu indukcije (za n = 0) lako dokazujemo, jer se svaki broj manji od 5 može predstaviti u traženom obliku.

Pretpostavimo da tvrdjenje važi za k − 1 i pokažimo da važi za k.

Neka je x < 5 · 2ᵏ proizvoljan takav broj. Ako je x < 5 · 2ᵏ⁻¹ onda prema induktivnoj hipotezi tvrdjenje važi. Inače x ∈ [5 · 2ᵏ⁻¹ , 5 · 2ᵏ). U tom slučaju važi:

    0 ≤ x − 5·2ᵏ⁻¹ < 5·2ᵏ − 5·2ᵏ⁻¹ = 5·2ᵏ⁻¹.

Broj x − 5·2ᵏ⁻¹ se prema induktivnoj hipotezi može predstaviti u obliku zbira različitih brojeva manjih od 5 · 2ᵏ⁻¹, pa x dobijamo kada tom zbiru dodamo još 5 · 2ᵏ⁻¹. Ne možemo imati ponavljanja medju sabircima jer ih po induktivnoj hipotezi nema u prethodnom zbiru, a broj 5 ⋅ 2ᵏ⁻¹ se ne može javiti u tom zbiru jer je broj x - 5 ⋅ 2ᵏ⁻¹ strogo manji od 5 ⋅ 2ᵏ⁻¹.

Zadatak 7

Dokazati da se svaka poštarina koja je pozitivni celi broj dinara veći od 7 može formirati korišćenjem samo markica od 3 i od 5 dinara.

Uputstvo: Broj n = 8 se može predstaviti kao zbir jedne markice od 3 i jedne od 5 dinara.

Pretpostavimo da je tvrdjenje tačno za prirodan broj n ≥ 8. Ako poštarina za n dinara uključuje neku markicu od 5 dinara, nju ćemo zameniti sa dve markice od po 3 dinara i ukupno povećati poštarinu za 1 dinar.

Ukoliko poštarina za n dinara ne uključuje nijednu markicu od 5 dinara, tada ona uključuje bar tri markice od 3 dinara, jer je n ≥ 8, pa je najmanji takav broj 9. U tom slučaju ćemo tri markice od po 3 dinara zameniti dvema od po 5 dinara.

Zadatak 8

Dokazati da se oblasti na koje ravan deli n kružnica sa po jednom povučenom tetivom mogu obojiti sa 3 boje tako da su susedne oblasti uvek obojene različitim bojama.

Uputstvo: Obeležimo boje sa 0,1,2. Baza indukcije je trivijalno dokaziva.

Pretpostavimo da se oblast sa n kružnica (sa povučenom tetivom) može obojiti na traženi način i dodajemo (n + 1)-vu kružnicu. Ona sa tetivom deli ravan na tri oblasti:

Zadatak 9

Neka je T kompletno binarno stablo visine h. Visina čvora u T je h umanjeno za rastojanje čvora od korena tako je npr. koren visine h a listovi su visine 0.

Dokazati da je suma visina svih čvorova u T jednaka 2ʰ⁺¹ − h − 2.

Uputstvo: Za h = 0 stablo sadrži samo koren i tvrdjenje se trivijalno dokazuje. Kompletno binarno stablo visine h + 1 se sastoji od dva kompletna binarna stabla visine h i korena (koji je visine h + 1).

Zadatak 10

Razmotrimo varijantu igre NIM. Igra počinje sa n šibica, dva igrača naizmenično uzimaju 1, 2 ili 3 šibice odjednom. Igrač koji uzme poslednju šibicu gubi.

Pokazati da ako svaki igrač igra po najboljoj mogućoj strategiji, prvi igrač pobedjuje za n = 4j, n = 4j + 2 ili n = 4j + 3, j ≥ 0, a drugi igrač za n = 4j + 1, j ≥ 0.

Uputstvo: Za j = 0 dokaz je trivijalan (treba razmotriti 4 bazna slučaja).

Pretpostavimo da tvrdjenje važi za j ≥ 0. Dokaz za j + 1 se izvodi svodjenjem 4 mogućnosti za broj n (da broj n daje redom ostatak 0, 1, 2 ili 3 pri deljenju sa 4) na 4 mogućnosti date induktivnom hipotezom.

Zadatak 11

Neka su d₁, d₂, … , dₙ prirodni brojevi i n ≥ 2. Dokazati da ako je

      n
      Σ  dᵢ = 2n - 2
     i=1

onda postoji onda postoji stablo sa n čvorova čiji su stepeni brojevi d₁, d₂, … , dₙ.

Uputstvo: Za n = 2 dokaz je trivijalan - dva čvora povezana granom.

Pretpostavimo da tvrdjenje važi za n − 1 brojeva. Neka je dato n prirodnih brojeva d₁, … , dₙ čija je suma 2n - 2.

Bar jedan od brojeva mora biti 1 (inače bi suma bila ≥ 2n), i bar jedan mora biti veći od 1 (inače bi suma bila ≤ n) - neka su to brojevi dᵢ i dⱼ. Ako izbacimo dᵢ iz skupa, a broj dⱼ umanjimo za 1, dobijamo skup za koji važi induktivna pretpostavka, pa postoji stablo sa tim stepenima. Ako u to stablo dodamo novi čvor stepena 1 (list) povezan sa čvorom stepena dⱼ − 1 ≥ 1 dobijamo opet stablo sa n čvorova i stepenima d₁, d₂, … , dₙ.

Zadatak 12

Neka je n pozitivan ceo broj. Dokazati da se 2ⁿ × 2ⁿ šahovska tabla sa jednim izbačenim poljem može pokriti korišćenjem delova L-oblika, gde ovi delovi prekrivaju 3 polja odjednom.

Uputstvo: Za n = 1 je tabla dimenzija 2 × 2 i tada se traženo pokrivanje dobija postavljanjem dela L-oblika na odgovarajući način.

Pretpostavimo da tvrdjenje važi za tablu veličine 2ⁿ × 2ⁿ i pokažimo da važi za tablu veličine 2ⁿ⁺¹ × 2ⁿ⁺¹.

Podelimo tablu na 4 table veličine 2ⁿ × 2ⁿ. Iz tri podtable nije izbačeno nijedno polje, a iz četvrtog jeste - ona se po induktivnoj hipotezi može prekriti. Na kratko izbacimo iz svake od podtabli po jedno polje (koje?). One se onda po IH mogu prekriti delovima L-oblika, a ta tri izbačena polja možemo pokriti jednim delom L-oblika.

Zadatak 13

Pokazati da ako su a₁, a₂, … , aₙ različiti realni brojevi, tačno n − 1 množenja je potrebno da bi se izračunao njihov proizvod, bez obzira na to kako su umetnute zagrade u njihov proizvod.

Zadatak 14

Pokazati da ako je n prirodan broj veći od 1, onda se on može predstaviti kao proizvod prostih brojeva.

Uputstvo: Iskoristiti potpunu indukciju.

Zadatak 15

Šta nije u redu u sledećem dokazu?

Teorema: Za svaki nenegativan ceo broj n važi 5n = 0.

Dokaz:

Baza indukcije: 5 · 0 = 0

Induktivni korak: Pretpostavimo da je 5 · j = 0 za sve nenegativne cele brojeve j, tako da je 0 ≤ j ≤ k. Napišimo k + 1 = i + j, gde su i i j prirodni brojevi manji od k + 1. Prema induktivnoj hipotezi važi:

    5(k + 1) = 5(i + j) = 5i + 5j = 0 + 0 = 0.

Uputstvo: Ne možemo napisati k + 1 = i + j, jer za k = 0 ne postoje i i j manji od k + 1 koji u zbiru daju k + 1.

Zadatak 16

Naći grešku u sledećem dokazu (navesti rečenicu koja nije ispravna i objasniti zašto nije ispravna): Neka je dat neprazan skup obojenih klikera. Svi klikeri u tom skupu su iste boje.

Baza indukcije: Ako imamo skup koji sadrži samo jedan kliker, svi klikeri tog skupa su iste boje.

Induktivni korak: Pretpostavimo da je tvrdjenje tačno za svaki skup koji sadrži n klikera. Uzmimo skup A koji u sebi ima n + 1 kliker.

Fiksirajmo jedan kliker i označimo ga sa a. Skup A \ a u sebi sadrži tačno n klikera, tako da na osnovu induktivne hipoteze možemo da zaključimo da su svi klikeri u tom skupu iste boje npr. crvene.

Fiksirajmo sada neki drugi kliker iz skupa A \ a, npr. b. On je dakle crvene boje.

Na osnovu induktivne hipoteze skup A \ b u sebi sadrži sve klikere iste boje. Pošto se u njemu nalazi i kliker a, zajedno sa svim ostalim crvenim klikerima, i on mora biti crven. Dakle svi klikeri skupa A su crveni, tj. iste boje.