Vrijeme: 02:10

Indukcija - Teži 1

Susreli smo se već s klasičnom matematičkom indukcijom - ako pokažemo dvije stvari: neka tvrdnja vrijedi za n=1 (baza indukcije) i ukoliko tvrdnja vrijedi za n (pretpostavka indukcije), tada vrijedi i za n+1 (korak indukcije), pokazali smo da tvrdnja vrijedi za svaki prirodan broj n. Klasična matematička indukcija ima svoje varijacije, a s nekima od njih susrest ćemo se na ovom predavanju:

1. Što ako želimo pokazati da nešto vrijedi za parne brojeve? U bazi indukcije dokazat ćemo da tvrdnja vrijedi za n=2, a u koraku ćemo pokazati da ako tvrdnja vrijedi za n, tada vrijedi i za n+2.

2. Za dokaz da tvrdnja vrijedi za n+1 ponekad je potrebna pretpostavka da tvrdnja vrijedi za brojeve 1,2, \ldots, n, a ne samo n. U tom slučaju koristimo tzv. jaku indukciju i u praksi nema razlike, jaka indukcija od klasične razlikuje se samo u pretpostavci.

3. Što ako primjerice znam pokazati da ako tvrdnja vrijedi za n, tada vrijedi i za n-1, te da tvrdnja vrijedi za neki beskonačni niz prirodnih brojeva, recimo niz potencija broja 2? Tada "regresivna" indukcija govori da tvrdnja vrijedi za sve prirodne brojeve.

Upišite 1 za nastavak.