Matematična indukcija

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.

Neformalni opis matematične indukcije lahko predstavimo z ozirom na zaporedni pojav verižno padajočih domin.

Najenostavnejša in najsplošnejša oblika matematične indukcije dokazuje trditev za vsa naravna števila n v dveh korakih:

1. Trditev velja za n = 1.
2. Č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

1. bo prva domina padla.
2. Če pade domina, bo padla tudi sosednja, in iz tega lahko zaključimo, da bodo padle vse domine.

Zgled

Želimo dokazati trditev:

${\displaystyle 1+2+3+\cdots +n={\frac {n(n+1)}{2}}}$

za vsa naravna števila n. To je preprosta enačba za vsoto vseh naravnih števil do števila n. Dokaz, da enačba velja za vsa naravna števila n lahko izvedemo s pomočjo matematične indukcije.

Dokaz

Baza indukcije: Preverimo ali enačba velja za n = 1. Vsota prvega naravnega števila je seveda enaka 1, in ${\displaystyle {\frac {1\times (1+1)}{2}}=1}$. Enačba tako velja za n = 1. Če trditev označimo kot P(n), lahko pišemo P(1) velja. Sedaj moramo pokazati, da če enačba velja pri n = m, velja tudi za n = m + 1.

Indukcijska predpostavka: Predpostavimo, da enačba velja za n = m, oziroma:

${\displaystyle 1+2+\cdots +m={\frac {m(m+1)}{2}}\;.}$

Indukcijski korak: Če na obeh straneh prištejemo m + 1, dobimo:

${\displaystyle 1+2+\cdots +m+(m+1)={\frac {m(m+1)}{2}}+(m+1)\;.}$

Z upoštevanjem algebrskih pravil imamo:

${\displaystyle ={\frac {m(m+1)}{2}}+{\frac {2(m+1)}{2}}={\frac {(m+2)(m+1)}{2}}\;.}$

In tako:

${\displaystyle 1+2+\cdots +(m+1)={\frac {(m+1)((m+1)+1)}{2}}\;.}$

To je enačba za n = m + 1, in njene resničnosti še nismo pokazali. Predpostavili smo, da je resnična trditev P(m) in odtod P(m + 1). Simbolično smo pokazali, da velja:

${\displaystyle P(m)\Rightarrow P(m+1)\;.}$

Zaradi indukcije lahko zaključimo, da trditev P(n) velja za vsa naravna števila n.