Matematična indukcija

Iz Wikipedije, proste enciklopedije

Za druge pomene glejte 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.

Vsebina

1 Zgled
- 1.1 Dokaz
2 Posplošitve
3 Dokaz nove opredelitve matematične indukcije

[uredi] Zgled

Želimo dokazati trditev:

$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.

[uredi] Dokaz

Preverimo ali enačba velja za n = 1. Vsota prvega naravnega števila je seveda enaka 1, in 1×(1+2) / 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.

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

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

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

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

Z upoštevanjem algebrskih pravil imamo:

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

In tako:

$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:

$P(m) \Rightarrow P(m + 1) \; .$