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 .