Matematička indukcija

Matematička indukcija je metod matematičkog dokazivanja koji se obično koristi da se utvrdi da je dati iskaz tačan za sve prirodne brojeve. Ovo se vrši

• dokazivanjem da je prvi u beskonačnom nizu iskaza tačan, i zatim
• dokazivanjem da ako je neki iskaz u beskonačnom nizu iskaza tačan, onda je tačan i njemu sledeći iskaz

Matematičku indukciju ne treba shvatati kao oblik induktivnog rezonovanja, koje se smatra ne-rigoroznim u matematici (vidi problem indukcije). U stvari, matematička indukcija je oblik deduktivnog rezonovanja, i potpuno je rigorozna.

Istorija

Najraniji tragovi matematičke indukcije se mogu naći u Euklidovom dokazu da postoji beskonačno puno prostih brojeva, i Baskarinom ciklidnom metodu Forma dokaza matematičkom indukcijom se javlja u knjizi koju je napisao Al-Karadži oko 1000. godine, koji ju je između ostalog koristio da dokaže binomnu teoremu i Paskalov trougao.

Nijedan od ovih starih matematičara nije eksplicitno dao induktivnu hipotezu. Prvo rigorozno izlaganje principa indukcije je dao Frančesko Mauroliko, u svom delu Arithmeticorum libri duo (1575.), koji je koristio ovu tehniku da dokaže da je zbir prvih n neparnih celih brojeva jednak n². Indukciju su takođe nezavisno otkrili Švajcarac Jakob Bernuli i Francuzi Paskal i Ferma.

Formalni opis

Najjednostavniji i najuobičajeniji oblik matematičke indukcije dokazuje da neki iskaz važi za sve prirodne brojeve n. Ovaj dokaz se sastoji iz dva koraka:

1. Baza indukcije: pokazuje se da iskaz važi kada je n = 0.
2. Induktivni korak: pokazuje se da ako iskaz važi za n = m, onda isti iskaz važi i za n = m + 1.

Korišćenje reči ako u induktivnom koraku se naziva induktivnom hipotezom. Kako bi se sproveo induktivni korak, pretpostavlja se da induktivna hipoteza važi (tačnije da je iskaz tačan za n = m) i onda se koristi ova pretpostavka da se dokaže iskaz za n = m + 1.

Formalni opis matematičke indukcije se može ilustrovati efektom domina.

Ovaj metod funkcioniše na sledeći način. Prvo se dokaže da je iskaz tačan za početnu vrednost, a zatim se dokaže da je proces prelaska sa neke vrednosti na sledeću ispravan. Ako su oba dokazana, onda se do tačnosti iskaza za svaku vrednost može doći uzastopnim ponavljanjem ovog procesa. Ovo se može posmatrati kao efekat domina; Ako imamo dugačak niz domina, i ako smo sigurni da:

1. Prva domina može da padne
2. Koja god domina da padne, oboriće i sledeću dominu,

onda možemo da zaključimo da će sve domine pasti, ukoliko se obori prva domina.

Osnovna pretpostavka ili aksioma indukcije (prihvata se, ne dokazuje) je ispisana logičkim simbolima,

$\forall {\mbox{ predicates }}P,(P(0)\land \forall k[P(k)\Rightarrow P(k+1)])\Rightarrow \forall nP(n)$

gde je P dati iskaz, a n prirodan broj.

Korak 1. dokazati P(0) - formula važi za ceo broj 0.

Korak 2. dokazati da za svaki prirodan broj k, P(k) implicira P(k+1). Da bi se ovo sprovelo, pretpostavlja se da važi P(k) i pokazuje se da iz ove pretpostavke sledi da važi P(k+1). Ovo ne znači zamenu (k+1) u P(k) - ovo je vrlo česta greška koja se sastoji u pretpostavljanju onoga šta tek treba da se dokaže. Zajedno koraci 1. i 2. impliciraju da P(n) važi za svako n veće ili jednako 0. U opštem slučaju, ako je P(s) dokazano, gde s može biti negativan ceo broj (zamislimo domine numerisane od -20 pa naviše), onda P važi za svako n veće ili jednako s.

Primer

Pretpostavimo da želimo da dokažemo iskaz:

$1+2+3+\cdots +n={\frac {n(n+1)}{2}}$

Za sve prirodne brojeve n; obeležimo ovaj iskaz kao P(n). (Ovo je specijalni slučaj Faulhaberove formule.) Ovo je jednostavna formula za sumu pozitivnih prirodnih brojeva manjih ili jednakih broju n. Dokaz da je ovaj iskaz tačan za sve prirodne brojeve n sledi.

Proverimo da li je iskaz tačan za n = 1. Suma samog broja 1 je prosto 1. A 1(1 + 1) / 2 = 1. Znači, iskaz je tačan za n = 1. Dokazali smo da P(1) važi.

Sada moramo da pokažemo da ako iskaz važi kada je n = m, onda on takođe važi i kada je n = m + 1. Ovo se može izvesti na sledeći način.

Pretpostavimo da je iskaz tačan za n = m, tj,

$1+2+\cdots +m={\frac {m(m+1)}{2}}$

Dodavanjem m + 1 sa obe strane se ne menja jednakost:

$1+2+\cdots +m+(m+1)={\frac {m(m+1)}{2}}+(m+1)$

Algebarskom manipulacijom, sa desne strane dobijamo

$={\frac {m(m+1)}{2}}+{\frac {2(m+1)}{2}}={\frac {(m+2)(m+1)}{2}}={\frac {(m+1)(m+2)}{2}}={\frac {(m+1)((m+1)+1)}{2}}.$

Stoga imamo

$1+2+\cdots +(m+1)={\frac {(m+1)((m+1)+1)}{2}}$

Primetimo da je ovo ekvivalentno tvrđenju P(m + 1). Ovaj dokaz je kondicionalan: načinili smo pretpostavku da je P(m) tačno, i iz toga smo izveli P(m + 1). Stoga, ako je P(m) tačno, onda i P(m + 1) mora biti tačno. Simbolički, pokazali smo da

$P(m)\Rightarrow P(m+1).\,$

Sada, kako bismo završili, koristimo proces matematičke indukcije:

1. Znamo da je P(1) tačno.
2. Kako P(1) implicira P(1 + 1), tačno je i P(2).
3. Slično, kako P(2) implicira P(2 + 1), dobijamo P(3).
4. Sa P(3), dobijamo P(4).
5. Iz P(4), sledi P(5).
6. I tako dalje. (ovde nastupa aksioma matematičke indukcije.)
7. Možemo da zaključimo da P(n) važi za svaki prirodan broj n. Q.E.D.