Induktio

Matemaattinen induktio on todistusmenetelmä, joka on luonteeltaan rekursiivinen. Matemaattisella induktiolla todistaminen perustuu induktioperiaatteeseen, jonka avulla voidaan todistaa luonnollisia lukuja \(\mathbb{N} = \{1,2,3,\dotsc\}\) koskevia väitteitä.

Olkoon \(P\) jokin todistettava väite. Induktiotodistus koostuu kolmesta vaiheesta:

  1. Perusaskel. Osoitetaan esimerkillä, että ensimmäinen tapaus \(P(1)\) pitää paikkansa.
  2. Induktioaskel.
    • Induktio-oletus: Oletetaan, että väite \(P(n)\) on tosi jollakin arvolla \(n=k\in\mathbb{N}\). Huomaa, että perusaskeleen nojalla väite on tosi tapauksessa \(n=1\), joten induktio-oletus on mielekäs ainakin tässä tapauksessa.
    • Induktioväite: \(P(n)\) on tosi arvolla \(n=k+1\).
    • Todistus: Osoitetaan, että induktio-oletuksesta ja muista tunnetuista tuloksista seuraa induktioväite.
  3. Johtopäätös. Koska \(P(1)\) on tosi perusaskeleen nojalla, niin induktio-askel arvolla yksi osoittaa, että \(P(2)\) on tosi. Tällöin induktio-askel arvolla kaksi osoittaa, että \(P(3)\) on tosi. Jatkamalla tätä päättelyä voidaan todeta, että väite \(P(n)\) on tosi kaikilla \(n\in\mathbb{N}\).

Alla on pari tyypillistä esimerkkiä induktiotodistuksesta.

Esimerkki 1. Osoita, että \(1+2+\dotsb+n = \frac{n(n+1)}{2}\) kaikilla \(n\in\mathbb{N}\).

  1. Perusaskel. Kun \(n=1\), niin väite \(1=\frac{1\cdot 2}{2}\) on triviaalisti totta.
  2. Induktioaskel.
    • Induktio-oletus: Oletetaan, että väite on tosi jollakin arvolla \(n=k\in\mathbb{N}\), eli on voimassa \(1+2+\dotsb+k = \frac{k(k+1)}{2}\).
    • Induktioväite: \(1+2+\dotsb+k + (k+1) = \frac{(k+1)(k+2)}{2}\).
    • Todistus: Soveltamalla induktio-oletusta nähdään, että \[\begin{aligned} 1+2+\dotsb+k + (k+1) & = (1+2+\dotsb + k) + (k+1)\\ & = \frac{k(k+1)}{2} + \frac{2(k+1)}{2}\\ & = \frac{(k+1)(k+2)}{2}. \end{aligned}\]
  3. Johtopäätös. Induktioperiaatteen nojalla väite pätee kaikilla \(n\in\mathbb{N}\).

Esimerkki 2. Osoita, että \(1^2+2^2+\dotsb+n^2 = \frac{n(n+1)(2n+1)}{6}\) kaikilla \(n\in\mathbb{N}\).

  1. Perusaskel. Kun \(n=1\), niin väite \(1^2=\frac{1\cdot 2\cdot 3}{6}\) on triviaalisti totta.
  2. Induktioaskel.
    • Induktio-oletus: Oletetaan, että väite on tosi jollakin arvolla \(n=k\in\mathbb{N}\), eli on voimassa \(1^2+2^2+\dotsb+k^2 = \frac{k(k+1)(2k+1)}{6}\).
    • Induktioväite: \(1^2+2^2+\dotsb+k^2 +(k+1)^2 = \frac{(k+1)(k+2)(2(k+1)+1)}{6}\).
    • Todistus: Soveltamalla induktio-oletusta nähdään, että \[\begin{aligned} 1^2+2^2+\dotsb+k^2 + (k+1)^2 & = (1^2+2^2+\dotsb + k^2) + (k+1)^2\\ & = \frac{k(k+1)(2k+1)}{6} + \frac{6(k+1)^2}{6}\\ & = \frac{(k+1)\big((2k^2+k)+(6k+6) \big)}{6}\\ & = \frac{(k+1)(k+2)(2(k+1)+1)}{6}. \end{aligned}\]
  3. Johtopäätös. Induktioperiaatteen nojalla väite pätee kaikilla \(n\in\mathbb{N}\).