Svaki neprazan podskup prirodnih brojeva ima minimalni elemenat u odnosu na relaciju <. Zahvaljujući ovoj osobini mažemo koristiti sledeći princip matematičke indukcije.
Teorema (Matematička indukcija na N) Tvrdđnje T(n); n ∈ N je tačno za svaki prirodan broj n ∈ N ako:
- Za n = 1, T(n) odnosno T(1) je tačno tvrđnje;
- Iz pretpostavke da je za proizvoljno n ∈ N tačno tvrđnje T(n) sledi da je T(n + 1) tačno tvrđenje , odnosno implikacijaT(n)⇒T(n + 1) je tačna za svaki prirodan broj n.
Matematička indukcija se koristi za dokazivanje tvrđnja koja zavisi od prirodnog broja n i važe na nekom podskupu prirodnih brojeva n0, n0+1, …
U dokazivanju tvrđenja koristićemo sledeće korake:
- Proverimo da li je tvrdjenje tačno za n = 1
- Predpostavimo da je tvrdjenje tačno za n = k
- Dokazujemo da je tvrdjenje tačno za n = k+1
Primena indukcije na dokazivanje deljivosti brojeva
