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)
.
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)
.
Koristeći princip matematičke indukcije dokazati da za svako n ∈ N
važi:
n qⁿ⁺¹ - 1
Σ qⁱ = ————————
i=0 q - 1
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)
.
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.
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
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.
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ᵏ⁻¹
.
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.
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:
(i + 1) % 3
(i − 1) % 3
.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
).
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.
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ₙ
.
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.
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.
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.
Š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
.
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.