Matematična indukcija
vrsta matematičnega dokazovanja / From Wikipedia, the free encyclopedia
Za druge pomene glej Indukcija.
Matemátična ali popólna indúkcija je v matematiki metoda dokaza, ki se običajno uporablja za dokazovanje ali je dana trditev ali izrek resničen za vsa naravna števila ali za vse člene neskončnega zaporedja. Nekoliko splošnejša oblika dokaza, ki se uporablja v matematični logiki in računalništvu, kaže, da so lahko izrazi, ki se jih da ovrednotiti, enakovredni. To je znano kot strukturalna indukcija.
Najenostavnejša in najsplošnejša oblika matematične indukcije dokazuje trditev za vsa naravna števila n v dveh korakih:
- Trditev velja za n = 1.
- Če velja trditev za n = m, potem iz tega sledi trditev tudi za n = m + 1.
Da razumemo zakaj sta dovolj dva koraka, je pripravno pomisliti na pojav domine. Če imamo eno dolgo vrsto domin, smo lahko prepričani, da
- bo prva domina padla.
- Če pade domina, bo padla tudi sosednja, in iz tega lahko zaključimo, da bodo padle vse domine.