Ero sivun ”Matemaattinen induktio” versioiden välillä

163 merkkiä lisätty ,  9 vuotta sitten
Hankalampi asia vasta johdannon jälkeen, pientä muokkausta kaavoissa
[arvioimaton versio][katsottu versio]
Ei muokkausyhteenvetoa
(Hankalampi asia vasta johdannon jälkeen, pientä muokkausta kaavoissa)
'''Matemaattinen induktio''' on [[matemaattinen todistus]]menetelmä, joka kuuluu matemaattisen [[algebra]]n päähaaraan.
 
Matemaattinen induktio perustuu ''induktioperiaatteeseen'', jolla todistetaan luonnollista lukua <math>n</math> koskeva väite todeksi kaikilla luvun <math>n</math>:n arvoilla. Teknisesti induktiotodistus koostuu kolmesta vaiheesta:
Toisin kuin [[Induktiivinen päättely|induktiivisessa päättelyssä]], matemaattiseen induktioon ei sisälly [[Induktion ongelma|Humen ongelmaa]], sillä matemaattinen induktio on [[rekursio]]on perustuvaa todistamista eli pätevää [[deduktiivinen päättely|deduktiivista päättelyä]]. Todistus perustuu rekursiorelaation avulla määriteltyyn äärettömän joukon säännönmukaisuuteen, joka todistuksessa yleistetään koko joukkoon, esimerkiksi [[luonnolliset luvut|luonnollisten lukujen]] joukkoon. Matemaattinen induktio voidaan myös samaistaa [[Induktiivinen_päättely#T.C3.A4ydellinen_induktio|täydellisen induktion]] kanssa, sillä siinä käydään rekursiivisesti kaikki mahdolliset yksittäistapaukset läpi.<ref name=cog121/><ref name=vtt/>
 
Matemaattinen induktio perustuu ''induktioperiaatteeseen'', jolla todistetaan luonnollista lukua <math>n</math> koskeva väite todeksi kaikilla <math>n</math>:n arvoilla. Teknisesti induktiotodistus koostuu kolmesta vaiheesta:
 
# Perusaskel
#* Todistus: todistetaan, että induktio-oletuksesta seuraa induktioväite
# Johtopäätös
#* Induktioaskeleessa todistettiin, että <math>P(n)</math> on tosi aina seuraavalla luvun <math>n</math>:n arvolla. Koska <math>P(0)</math> on tosi, niin myös <math>P(n)</math> on tosi kaikilla luonnollisilla luvuilla <math>n</math>:n luonnollisilla arvoilla.
 
Toisin kuin [[Induktiivinen päättely|induktiivisessa päättelyssä]], matemaattiseen induktioon ei sisälly [[Induktion ongelma|Humen ongelmaa]], sillä matemaattinen induktio on [[rekursio]]on perustuvaa todistamista eli pätevää [[deduktiivinen päättely|deduktiivista päättelyä]]. Todistus perustuu rekursiorelaation avulla määriteltyyn äärettömän joukon säännönmukaisuuteen, joka todistuksessa yleistetään koko joukkoon, esimerkiksi [[luonnolliset luvut|luonnollisten lukujen]] joukkoon. Matemaattinen induktio voidaan myös samaistaa [[Induktiivinen_päättely#T.C3.A4ydellinen_induktio|täydellisen induktion]] kanssa, sillä siinä käydään rekursiivisesti kaikki mahdolliset yksittäistapaukset läpi.<ref name=cog121/><ref name=vtt/>
 
==Esimerkki==
Todistetaan oikeaksi kaava <math>0+1+2+ \dots +n=\frac{n(n+1)}{2}</math>.
:<math>0+1+2+ \dots +n=\frac{n(n+1)}{2}.</math>
 
# '''Perusaskel:'''
#: Näytetään, että ''<math>P(0)''</math> pätee:
#: <math>0 = \frac{0 \cdot (0+1)}{2}</math>
# '''Induktioaskel:'''
#: ''Induktio-oletus: <math>P(n)</math>'' on tosi. ''(Varmaksi tiedetään jo siis <math>P(0)</math> paikkansapitävyys.)''.
#: ''Induktioväite: <math>P(n + 1)</math>'' on tosi. Toisin sanoen
#: <math>0+1+2+ \dots +n+(n+1) = \frac{(n+1) \cdot ((n + 1)+1)}{2}.</math>.
#: Induktio-oletuksen nojalla voidaan tehdä sijoitus <math>(0 + 1 + 2 + \dots + n) = n(n+1)/2</math>, jolla yhtälön vasen puoli saadaan muotoon
#: <math>\frac{n \cdot (n+1)}{2}+(n+1).</math>.
#: Jos tämä voidaan esittää samassa muodossa <math>\frac{(n+1)kuin \cdotinduktioväitteen ((noikea + 1)+1)}{2}\ </math>puoli, onniin induktiotodistus on saatettu loppuun. Induktioväite on tosi, koska
#: <math>\begin{align}
\frac{n \cdot (n+1)}{2}+(n+1) & = (n+1) \left( \frac{n}{2} + 1 \right) \\
& = (n+1)\left( \frac{n}{2} + \frac{2}{2} \right) \\
& = \frac{(n+1)(n + 2)}{2} \\
& = \frac{(n+1) \cdot ((n + 1) + 1)}{2} \\.
&& \Box
\end{align}
</math>
# '''Johtopäätös:'''
 
#: Tästä siis seuraa, että kaava pätee arvolla ''<math>n + 1''</math>. Kaavan todettiin alussa pitävän paikkansa, kun <math>n = 0</math>. Näiden kahden seurauksena kaava pitää paikkansa myös arvoilla <math>n \isinin \{ 0,\ (0 + 1),\ (0 + 1) + 1,\ \dots \} = \mathbb{N}. \qquad \Box</math>.
 
==Katso myös==
*[[Induktiivinen päättely]] - (yksittäisestä tapauksesta yleiseen tapaukseen)
*[[Deduktiivinen päättely]] - (yleisestä tapauksesta yksittäiseen tapaukseen)
 
==Lähteet==
56 239

muokkausta