1 - Indukcija Uvod
Kvaliteta:
Avg: 0,0Težina:
Avg: 0,0 Matematička indukcija je metoda dokazivanja koja se najčešće koristi kada želimo dokazati da neka tvrdnja vrijedi za sve prirodne brojeve. Sastoji od tri dijela, baze, u kojoj dokazujemo tvrdnju za neki početni broj, najčešće 1, pretpostavke, u kojoj pretpostavljamo da tvrdnja vrijedi za neki prirodan broj
i koraka u kojemu koristeći pretpostavku pokazujemo da tvrdnja vrijedi i za
. Na taj način smo dokazali da tvrdnja zaista vrijedi za sve prirodne brojeve. Jednostavan način za vizualizirati indukciju je zamisliti brojeve kao domine. U koraku pokazujemo da, ako padne domina broj
, ona će srušiti dominu
, a u bazi pokazujemo da
će prva domina stvarno pasti. Tada smo sigurno da će sve domine pasti.
Primjer jedne jednostavne indukcije:
Dokažimo da je
za ![n \in \mathbb{N}](/media/m/2/b/a/2ba27c6141ca415bb86bae1d237f1fac.png)
Baza
![n=1](/media/m/4/e/4/4e466fe58c2a8f6389234c5c673f069c.png)
![1+1>1](/media/m/5/5/5/5557cd5d58459c6f21a850df8ba0a25b.png)
![2>1](/media/m/6/1/6/61687a6051a67447db0a7b164b0fb7ce.png)
Ova tvrdnja očito vrijedi
Pretpostavka
Pretpostavimo da vrijedi
![n+1>n](/media/m/a/7/d/a7df57a284afe0bacdb2df02ce39627e.png)
za neki prirodan broj
.
Korak
Želimo dokazati da
to jest ![n+2>n+1](/media/m/b/5/6/b5692efa1ee2984c16772305a64e05b7.png)
Iz pretpostavke znamo da je
, pa pridodajmo sada na obje strane nejednakosti ![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
dobivamo:
![(n+1)+1>n+1](/media/m/3/a/f/3afcbafd0c64d44d5c209d9baa3675ed.png)
![n+2>n+1](/media/m/b/5/6/b5692efa1ee2984c16772305a64e05b7.png)
Čime zavrsava korak indukcije
Kako smo pokazali da tvrdnja vrijedi za
, i da ako vrijedi za
, vrijedi i za
, očito ta tvrdnja vrijedi za svaki prirodni broj.
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n+1](/media/m/2/a/7/2a7327e09a84d01a602088c9f045cbde.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n+1](/media/m/2/a/7/2a7327e09a84d01a602088c9f045cbde.png)
će prva domina stvarno pasti. Tada smo sigurno da će sve domine pasti.
Primjer jedne jednostavne indukcije:
Dokažimo da je
![n+1>n](/media/m/a/7/d/a7df57a284afe0bacdb2df02ce39627e.png)
![n \in \mathbb{N}](/media/m/2/b/a/2ba27c6141ca415bb86bae1d237f1fac.png)
Baza
![n=1](/media/m/4/e/4/4e466fe58c2a8f6389234c5c673f069c.png)
![1+1>1](/media/m/5/5/5/5557cd5d58459c6f21a850df8ba0a25b.png)
![2>1](/media/m/6/1/6/61687a6051a67447db0a7b164b0fb7ce.png)
Ova tvrdnja očito vrijedi
Pretpostavka
Pretpostavimo da vrijedi
![n+1>n](/media/m/a/7/d/a7df57a284afe0bacdb2df02ce39627e.png)
za neki prirodan broj
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
Korak
Želimo dokazati da
![(n+1)+1>n+1](/media/m/3/a/f/3afcbafd0c64d44d5c209d9baa3675ed.png)
![n+2>n+1](/media/m/b/5/6/b5692efa1ee2984c16772305a64e05b7.png)
Iz pretpostavke znamo da je
![n+1>n](/media/m/a/7/d/a7df57a284afe0bacdb2df02ce39627e.png)
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
dobivamo:
![(n+1)+1>n+1](/media/m/3/a/f/3afcbafd0c64d44d5c209d9baa3675ed.png)
![n+2>n+1](/media/m/b/5/6/b5692efa1ee2984c16772305a64e05b7.png)
Čime zavrsava korak indukcije
Kako smo pokazali da tvrdnja vrijedi za
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n+1](/media/m/2/a/7/2a7327e09a84d01a602088c9f045cbde.png)
Izvor: Nepoznato