Matematicka  indukcija je poseban metod matematičkog dokazivanja koji nam ne dozvoljava da donosimo zakljucke o opstem pravilu na osnovu pojedinacnih slucajeva, bez odredjenih dokaza.

Aksiom matematičke indukcije glasi ovako: Ako je sa osobinom:

onda je

Ova aksioma pruza mogucnost za dokazivanje velikog broja teorema koje se odnose na prirodne brojeve.

Metoda matematicke indukcije cesto se naziva i principom matematicke indukcije. Sastoji se u sljedecem:

Neka je iskaz koji se odnosi na prirodan broj . Tada je on tacan za sve prirodne brojeve ako su ispunjeni uslovi:
je tacan iskaz,
je tacan iskaz za sve math>\forall n \in \mathbb{N}</math>

Ako je tacno , s obzirom na

tacno je
tacno je .

Zakljucujemo da je tacno je Zato princip matematicke indukcije usvajamo kao tacan.

je osnova (baza) indukcije
je indukcijski korak
je indukcijska hipoteza (pretpostavka).

Primjena metoda matematicke indukcije u pokusaju dokazivanja nekog tvrdjenja podrazumjeva dokaz baze indukcije i induktivnog koraka, jer su to dva nezavisna tvrdjenja tj. ni jedno ne proizilazi iz onog drugog. Ako nesto od ova dva uslova nije tacno, onda je i tvrdnja netacna. Ako se ne provjere oba uslova moze doci do greske.

Primjer:

Za
Tvrdnja nije tacna

Cesta greska je da se dokaze indukcija a ne dokaze baza.

Vazi za

Ali ne vazi za

Princip matematicke indukcije razlikuje se empirijske indukcije koja se sastoji u posmatranju ili eksperimentisanju, najcesce u prirodnim naukama. Ovakvo rasuđivanje ima svoju primjenu i u matematici jer je pomoću njega otkriveno, a kasnije dokazano vise vaznih stavova, ali ponekad moze dovesti i do formulacija tvrdjenja za koje se pokazuje da su pogresna.Francuski matematicar Pjer Ferma posmatrajuci brojeve.

koji su prosti za
izveo pretpostavku da su svi brojevoi oblika

prosti. Kasnije je utvrđeno da je broj

djeljiv sa , a isto tako da su i

slozeni brojevi za

Empirijskom indukcijom, kao sto je vec receno, mogu se naslutiti neke formule (jednakosti, nejednakosti i slicno) koje zavise od prirodnog broja , a metod matematicke indukcije omogucuje da u mnogim slucajevima utvrdimo da li je postavljena hipoteza tacna ili nije. Princip matematicke indukcije nije dokazan vec detaljno objasnjen.

Primjer

Svaki neprazan podskup A skupa N ima najmanji element.

Dokaz:

Neka je

Pretpostavimo da je A neprazan i da nema najmanji element.
Neka je C skup svih prirodnih brojeva koji su manji od svakog elementa skupa A.
Dokazacemo primjenom aksiome indukcije da je C=N.

slijedi iz pretpostavke da A nema najmanji element i da je 1 najmanji u skupu N. Pretpostavimo da je . Treba da pokažemo da je

U suprotnom bi bio najmanji u
A,sto protivreci pretpostavci da u A ne postoji najmanji element.
Znaci . Odavde slijedi da je A prazan skup sto je u kontradikciji sa pretpostavkom.
Vratimo se sada na dokaz principa matematicke indukcije.
Pretpostavimo da su , ,.... , tvrdnje za koje vazi
  1. tacno,
  2. za svako iz tacnosti slijedi tacnost

Regresivna indukcija[uredi | uredi izvor]

Istinitost nekog metoda , za svako po metodu regresivne indukcije slijedi iz:

  1. je tacno za beskonacno mnogo prirodnih brojeva
  2. za sve prirodne brojeve (n >1)P(n)= >P(n-1) je tacan iskaz.

Primer Dokazati da za sve prirodne brojeve i sve nenegativne realne brojeve vazi nejednakost aritmeticke i geometrijske sredine

Prvo matematickom indukcijom po dokazujemo da tvrdjenje vazi za sve prirodne brojeve oblika . za imamo

To znaci nejednakoxt vazi za

Pretpostavimo sada da je nejednakost tačna za neki prirodan broj i izaberimo

Dokazalismo da nejednakost vazi i za , pa zakljucujemo da vazi za sve prirodne brojeve. U datoj nejednakosti za jednaskost važi ako i samo ako je .

Rekurentna indukcija[uredi | uredi izvor]

Postoje tvrdnje koje se dokazuju metodom matematicke indukcije, ali je pri dokazivanju indukcijskog koraka prakticnije pretpostaviti i dokazati . Drugacije rečeno, ne cini se korak sa ka , većc sa nekoliko koji prethode ka . Ako indukcijski korak ima k pretpostavki ovaj princip se moze zapisati:

Ovaj princip matematicke indukcije je ekvivalentan osnovnom principu.

Primjer

Nela je

, ...
za

Dokazati

i za i
vazi za i

Jednakost vrijedi za sve prirodme brojeve

Transfinitna indukcija[uredi | uredi izvor]

Kod pojedinih tvrdnji o prirodnim brojevima za dokaz da važi treba dokazati sljedece

  1. tacan iskaz
  2. ako su tacni iskazi onda je ) tacan iskaz.

Ova indukcija se zapisuje na sljedeci nacin

Primjer Dokazati da je svaki prirodan broj prost ili je proizvod prostih brojeva.

  1. za broj 2 je prost pa je tvrdnja tacna.
  2. neka je prirodan broj i neka tvrdnja vaz za . broj n je prost pa je tvrdnja tacna.

Ako je slozen broj onda je za i prirodne brojeve manje od . Za i vazi indukcijska pretpostavka pa su oni prosti brojevi. ili proizvod prostih brojeva pa je .

Community content is available under CC-BY-SA unless otherwise noted.