Matematičke formule

Princip matematičke indukcije

Pretpostavimo da imamo neku tvrdnju u čijoj se formulaciji pojavljuju prirodni brojevi. Neka je to tvrdnja T(n). Neka ta tvrdnja vrijedi za prirodni broj 1, tj. T(1) je istinita. Ako iz pretpostavke da je tvrdnja valjana za proizvoljan broj   (tj. Pretpostavimo da T(k) vrijedi), slijedi da je ona valjana i za njegovog neposrednog slijedbenika k+1, tada vrijedi i za svaki prirodni broj  .
Princip matematičke indukcije sastoji se iz 3 koraka:

1.    Baza indukcije (n=1)  -Tvrdnja vrijedi za broj 1. T(1) je istinita.
2.    Pretpostavka indukcije (n=k)  -Tvrdnja vrijedi za prirodan br n=k. T(k) je istinita.
3.    Korak indukcije (n=k+1)  – Koristeći pretpostavku  indukcije, pokažemo da tvrdnja vrijedi i za prirodni broj n=k+1, tj. T(k) je istinita   T(k+1) istinita.