Školjka

%V0 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, [b]baze[/b], u kojoj dokazujemo tvrdnju za neki početni broj, najčešće 1, [b]pretpostavke[/b], u kojoj pretpostavljamo da tvrdnja vrijedi za neki prirodan broj $n$ i [b]koraka[/b] u kojemu koristeći pretpostavku pokazujemo da tvrdnja vrijedi i za $n+1$. 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 $n$, ona će srušiti dominu $n+1$, 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 $n+1>n$ za $n \in \mathbb{N}$ [b]Baza[/b] $n=1$ $1+1>1$ $2>1$ Ova tvrdnja očito vrijedi [b]Pretpostavka[/b] Pretpostavimo da vrijedi $n+1>n$ za neki prirodan broj $n$. [b]Korak[/b] Želimo dokazati da $(n+1)+1>n+1$ to jest $n+2>n+1$ Iz pretpostavke znamo da je $n+1>n$, pa pridodajmo sada na obje strane nejednakosti $1$ dobivamo: $(n+1)+1>n+1$ $n+2>n+1$ Čime zavrsava korak indukcije Kako smo pokazali da tvrdnja vrijedi za $1$, i da ako vrijedi za $n$, vrijedi i za $n+1$, očito ta tvrdnja vrijedi za svaki prirodni broj.