"
  1. Insinöörimatematiikka 123 »
  2. Joukko-opin, logiikan ja todistamisen perusteita »
  3. Induktiotodistus

Induktiotodistus

Kuvitellaan pitkä jono dominopalikoita. Milloin ne kaikki saadaan kaatumaan koskemalla vain jonon ensimmäiseen palikkaan? Videon perusteella voitaisiin muotoilla seuraavat ehdot.

  1. Ensimmäinen palikka saadaan kaadettua.
  2. Jokainen kaatuva palikka kaataa myös seuraavan palikan.

Näistä molempien on toteuduttava, jotta kaikki palikat kaatuvat. Tulkitaan nyt jokainen dominopalikka väitteeksi \(p(n)\), jonka sisältö riippuu palikan järjestysnumerosta \(n\) jonossa. Jos jonon \(k\). palikka kaatuu, lause \(p(k)\) on tosi. Jos puolestaan \(k\). palikka kaatuessaan kaataa myös palikan \(k + 1\), lause \(p(k) \rightarrow p(k + 1)\).

Mitä tapahtuu, jos lause \(p(1)\) on tosi ja lause \(p(k) \rightarrow p(k + 1)\) on tosi jokaisella luonnollisella luvulla \(k\)?

Lause.

Olkoon \(n\) luonnollinen luku ja \(p(n)\) sitä koskeva väite. Jos

  1. lause \(p(1)\) on tosi
  2. aina, kun \(k \in \mathbb N\), lause \(p(k) \rightarrow p(k + 1)\) on tosi,

niin lause \(p(n)\) on tosi jokaisella \(n \in \mathbb N\). Tämä on induktioperiaate.

Matemaattinen induktio, eli induktioperiaate perustelee hyvin erityisen todistusmenetelmän. Induktiotodistus on mahdollinen silloin, kun todistettava väite \(p(n)\) koskee peräkkäisiä luonnollisia lukuja. Sillä on myös seuraava, yksinkertainen rakenne.

Todistus.

Todistetaan väite induktiolla.

  1. Alkuaskel. Osoitetaan, että lause \(p(1)\) on tosi.
  2. Induktioaskel. Osoitetaan, että lause \(p(k) \rightarrow p(k + 1)\) on tosi, kun \(k\) on luonnollinen luku. Tämä tapahtuu olettamalla, että lause \(p(k)\) on tosi (induktio-oletus, io) ja sen jälkeen todistamalla, että lause \(p(k + 1)\) on tosi (induktioväite).

Edellä osoitetun ja induktioperiaatteen nojalla väite \(p(n)\) on tosi kaikilla luonnollisilla luvuilla \(n\). \(\square\)

Esimerkki.

Osoita, että \(1+2+3+\cdots+n=\dfrac{n(n+1)}{2}\), kun \(n\in\mathbb N\).

Todistus.

Todistetaan väite induktiolla.

  1. Alkuaskel. Kun \(n = 1\), väite tulee muotoon

    \[1 = \frac{1 \cdot (1 + 1)}{2} = 1,\]

    mikä on tosi.

  2. Induktioaskel. Tehdään induktio-oletus, jonka mukaan

    \[1 + 2 + 3 + \ldots + k = \frac{k(k + 1)}{2},\]

    kun \(k\) on luonnollinen luku. Pyritään osoittamaan, että

    \[1 + 2 + 3 + \ldots + k + (k + 1) = \frac{(k + 1)(k + 2)}{2}.\]

    Induktio-oletuksen nojalla voidaan kirjoittaa

    \[\begin{split}\begin{aligned} 1 + 2 + 3 + \ldots + k + (k + 1) &= (1 + 2 + 3 + \ldots + k) + (k + 1) \\ &\stackrel{\text{io}}{=} \left(\frac{k(k + 1)}{2}\right) + k + 1 \\ &= \frac{k(k + 1) + 2(k + 1)}{2} = \frac{(k + 1)(k + 2)}{2}, \end{aligned}\end{split}\]

    eli induktioväite on tosi.

Induktioperiaatteen nojalla siis

\[1 + 2 + 3 + \ldots + n = \frac{n(n + 1)}{2}\]

kaikilla luonnollisilla luvuilla \(n\). \(\square\)

Esimerkki.

Todista Bernoullin epäyhtälö: jos \(1 + x \geq 0\), missä \(x \in \mathbb R\),

\[(1 + x)^n \geq 1 + nx\]

jokaiselle luonnolliselle luvulle \(n\).

Todistus.

Olkoon \(1 + x \geq 0\). Todistetaan väite induktiolla.

  1. Alkuaskel. Kun \(n = 1\), väite tulee muotoon \((1 + x)^1 \geq 1 + x\), mikä on tosi.

  2. Induktioaskel. Tehdään induktio-oletus, jonka mukaan \((1 + x)^k \geq 1 + kx\), kun \(k\) on luonnollinen luku. Pyritään osoittamaan, että \((1 + x)^{k + 1} \geq 1 + (k + 1)x\). Induktio-oletuksen ja luvun \(x\) määrittelyn nojalla voidaan kirjoittaa

    \[\begin{split}\begin{aligned} (1 + x)^{k + 1} &= (1 + x)^k(1 + x) \\ &\stackrel{\text{io}}{\geq} (1 + kx)(1 + x) \\ &= 1 + x + kx + kx^2 = 1 + (k + 1)x + \underbrace{kx^2}_{\geq 0} \\ &\geq 1 + (k + 1)x, \end{aligned}\end{split}\]

    eli induktioväite on tosi.

Induktioperiaatteen nojalla siis \((1 + x)^{n} \geq 1 + nx\) kaikilla luonnollisilla luvuilla \(n\). \(\square\)

Induktiotodistuksen alkuaskeleessa voidaan valita myös mikä tahansa muu luonnollinen luku kuin \(1\), mutta tällöin väite tulee todistetuksi vain kaikille tätä suuremmille luonnollisille luvuille.

Esimerkki.

Tutki, mistä luonnollisen luvun \(n\) arvosta alkaen \(2^n \leq n!\), ja todista väitteesi induktiolla. Luvun \(n\) kertoma (factorial) \(n!\) määritellään asettamalla

\[n!=1\cdot2\cdot3\cdot\cdots\cdot n.\]
Ratkaisu.

Tutkitaan lausekkeita \(2^n\) ja \(n!\), kun \(n = 1, 2, 3, \ldots\).

\[\begin{split}\begin{aligned} 2^1 = 2 &> 1 = 1! \\ 2^2 = 4 &> 2 = 1 \cdot 2 = 2! \\ 2^3 = 8 &> 6 = 1 \cdot 2 \cdot 3 = 3!\\ 2^4 = 16 &\leq 24 = 1 \cdot 2 \cdot 3 \cdot 4 = 4!\end{aligned}\end{split}\]

Siis kun \(n = 4\), lause \(2^n \leq n!\) on tosi. Todistetaan induktiolla, että \(2^n \leq n!\) aina, kun luonnollinen luku \(n \geq 4\).

  1. Alkuaskel. Tapaus \(n = 4\) käsiteltiin jo.

  2. Induktioaskel. Tehdään induktio-oletus, jonka mukaan \(2^k \leq k!\), kun \(k \geq 4\) on luonnollinen luku. Pyritään osoittamaan, että \(2^{k + 1} \leq (k + 1)!\). Koska \(k \geq 4\), niin \(2 < k + 1\), jolloin induktio-oletuksen nojalla voidaan kirjoittaa

    \[2^{k + 1} = 2 \cdot 2^k \stackrel{\text{io}}{\leq} 2 \cdot k! < k!(k + 1) = (k + 1)!,\]

    eli induktioväite on tosi.

Induktioperiaatteen nojalla siis \(2^n \leq n!\) kaikilla luonnollisilla luvuilla \(n \geq 4\).