Primjer 6: indukcija
Zadatak: Neka je čiji članovi zadovoljavaju rekurzivnu formulu
Ukoliko je prvi član niza jednak
dokažite da je
djeljiv s
.
Rješenje Primjetimo specifičnost rekurzije koja je zadana. Ukoliko bi umjesto pisalo
imalo bismo da je
, dakle i za
-vi član niza bismo dobili da je jednak kvadratu svojeg rednog broja. Dakle, slutimo da je zadani niz zapravo niz kvadrata prirodnih brojeva, odnosno
. Ukoliko to pokažemo tada iz
dobivamo
iz čega slijedi
.
Činjenicu da je možemo dobiti na dva načina: ili ju korištenjem dane rekurzije dobijemo direktno (takozvani "glavom-kroz-zid" pristup ili "gruba sila"; najčešće treba zbrojiti neke članove tog niza) ili ju dokažemo korištenjem principa matematičke indukcije.
Gruba sila
Ukoliko u rekurzivno zadanom nizu sljedeći član niza na jednostavan način ovisi o prethodnom često se isplati zbrojiti prvih članova niza
Slijedi da je
-ti član niza jednak
Primjetimo da u zagradi imamo sumu prvih
prirodnih brojeva. Budući da je suma prvih
prirodnih brojeva jednaka
slijedi da je
Korištenje principa matematičke indukcije
Tvrdimo da za svaki prirodan broj vrijedi
.
Po principu matematičke indukcije slijedi da tvrdnja vrijedi za svaki prirodan broj
.
Napomena: Kao rješenje unesite .