Matematična indukcija je splošna metoda dokazovanja izjav, ki naj bi veljale za vsa naravna števila (ali za vsa števila iz neke zaporedne množice, npr. od neke začetne vrednosti naprej). Temelji na dveh ključnih korakih, ki skupaj omogočata, da resničnost izjave "podrsne" od začetnega primera na vsa naslednja.

Osnovna ideja

  • Osnovni korak (base case): pokažemo, da izjava drži za prvo (ali za določeno začetno) vrednost n (npr. n = 1 ali n = m).
  • Indukcijski korak: predpostavimo, da izjava velja za nek poljuben, a fiksiran n = n0 (to se imenuje indukcijska predpostavka). Na podlagi te predpostavke dokažemo, da izjava velja tudi za n = n0 + 1.

Če sta oba koraka uspešno opravljena, potem izjavno resničnost za n = 1 prenašamo na n = 2, nato na n = 3 in tako naprej — torej na vsa nadaljnja naravna števila.

Formalna struktura dokaza z indukcijo

  1. Jasno napišite trditev P(n), ki jo želite dokazati.
  2. Base case: dokažite P(n0) za izbrano začetno n0 (pogosto n0 = 1).
  3. Indukcijska predpostavka: predpostavite, da P(n0) drži za neko proizvoljno, a fiksno n0 ≥ začetka.
  4. Indukcijski korak: iz predpostavke P(n0) dokažite P(n0 + 1).
  5. Zaključek: ker P(n0) velja in vsaka veljavnost pri n0 implicira veljavnost pri n0 + 1, sledi, da P(n) velja za vse n ≥ n0.

Opombe in nasveti

  • Indukcijska spremenljivka je običajno označena z n; v zapisu se pogosto pojavi kot n n — to je tista spremenljivka, po kateri indukcija poteka.
  • Včasih je priročno dokazovati obliko P(n) z množenjem ali deljenjem, da se izognemo ulomkom; to je le algebraični trik, pomembno je, da algebra ostane pravilna.
  • Obstaja tudi močna indukcija (complete induction), kjer v indukcijski predpostavki predpostavimo veljavnost za vse vrednosti ≤ n0 in na tej podlagi dokažemo veljavnost za n0+1. Ta različica je uporabna, kadar P(n0+1) zahteva več predhodnih primerov kot samo n0.
  • Indukcija je logično ekvivalentna principu dobrega urejanja naravnih števil: vsako neprazno podmnožico naravnih števil ima najmanjšega člana.

Primer — vsota prvih n naravnih števil

Dokazali bomo formulo za vsoto prvih n naravnih števil:

1 + 2 + 3 + ... + (n − 1) + n = n(n + 1) / 2.

V simbolični obliki:

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)}

Dokaz z indukcijo:

1. Definicija trditve P(n): P(n) je izjava "1 + 2 + ... + n = n(n+1)/2". Včasih, da se izognemo ulomkom, množimo celo enačbo z 2 in preverimo ekvivalentno obliko

2∑_{k=1}^{n} k = n(n+1) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)}

2. Osnovni korak (n = 1):

Levo: 1. Desno: 1(1+1)/2 = 1. Zato P(1) drži. V zapisu brez ulomkov:

2\sum_{k=1}^{1}k = 2(1) = 2 {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} — rezultat je skladen z desno stranjo n(n+1).

3. Indukcijska predpostavka: Naj bo za neko fiksno n = n0 res, da velja

2\sum_{k=1}^{n_{0}}k = n_{0}(n_{0}+1) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)}.

4. Indukcijski korak (dokaz za n0 + 1): Potrebno je pokazati

2\sum_{k=1}^{n_{0}+1}k = (n_{0}+1)(n_{0}+2) {\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k}.

Začnemo z razčlenitvijo vsote:

2\left(\sum_{k=1}^{n_{0}}k + (n_{0}+1)\right) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)}.

Uporabimo indukcijsko predpostavko 2\sum_{k=1}^{n_{0}}k = n_{0}(n_{0}+1) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),} in dobimo:

2\sum_{k=1}^{n_{0}+1}k = n_{0}(n_{0}+1) + 2(n_{0}+1) = (n_{0}+1)(n_{0}+2) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)}.

Deljenjem z 2 pridemo do izvirne oblike:

∑_{k=1}^{n_{0}+1} k = (n_{0}+1)(n_{0}+2)/2, torej P(n0+1) drži. S tem je indukcijski korak zaključen.

Ker sta osnovni korak in indukcijski korak dokazana, sledi, da velja formula za vsa naravna števila n ≥ 1.

Pogoste napake

  • Preskočitev preverjanja osnovnega primera ali izbira napačnega začetka (n0) — indukcija deluje le od izbranega začetka naprej.
  • Nepravilno formulirana indukcijska predpostavka (npr. da predpostavljamo nekaj več, kot je dovoljeno) — predpostavka mora biti "za nek proizvoljni, a fiksni n0".
  • Napačna algebra pri prehodu iz P(n0) na P(n0+1) — preverite vse računske korake natančno.

Razširitve

  • Močna indukcija: predpostavite resničnost za vse vrednosti ≤ n0 in na tej podlagi dokažite za n0+1 (uporabno pri zaporedjih, kjer je naslednji člen odvisen od več prejšnjih).
  • Indukcija se uporablja tudi pri strukturah, kot so drevesa ali grafi, kjer indukcijski korak poteka po številu vozlišč ali robov.

Indukcija je zato temeljno orodje pri dokazovanju trditev o zaporedjih, vsotah, neenakostih, deljenosti in mnogih drugih lastnostih, ki so definirane za naravna števila ali druge dobro urejene množice.