Induksjonsbevis
Bevis ved induksjon er delt i to trinn, induksjonsgrunnlaget og induksjonsstrinnet.
La <math>U(n)</math> være et åpent utsagn som gjelder for alle <math>n \geq n_0</math>
Dersom
1. induksjonsgrunnlaget <math>U(n_0)</math> er sann
og
2. induksjonstrinnet <math>U(k) \Rightarrow U(k+1),\quad k\geq n_0 </math> er sann,
så er <math>U(n)</math> sann for alle <math>n \geq n_0.</math>
Prinsippet for induksjonsbevis illustreres enklest via et konkret eksempel: La oss si at vi ønsker å bevise formelen
\[ \sum_{i=1}^{n}i=\frac{n(n+1)}{2}\, \qquad \forall n \in \mathbb{N} \]
Trinn 1
Det første vi gjør er å verifisere at formelen gjelder for spesialtilfellet <math>n=1</math>. Dette er trivielt siden <math>\sum_{i=1}^{1}i=1</math> og <math>\frac{1\cdot (1+1)}{2}=1</math>; høyresiden er lik venstresiden.
Trinn 2 (induksjonstrinnet)
I induksjonstrinnet antar vi at formelen gjelder for en bestemt verdi av n, si <math>n=k</math> og utleder deretter via kjente regneregler at formelen også gjelder for <math>n=k+1</math>. Dersom vi lykkes, vil dette indusere en dominoeffekt: Fra trinn 1 vet vi at formelen gjelder for <math>n=1</math> og trinn 2 sikrer at formelen gjelder for <math>n=2</math> (og på samme måte at formelen gjelder for <math>n=3</math> etc.).
I det konkrete eksempelet vil induksjonstrinnet se slik ut:
Vi antar at formelen er riktig for <math>n=k</math>:
\[ \sum_{i=1}^{k}i=\frac{k (k+1)}{2} \]
Vi undersøker så summen når <math>n=k+1</math> ved å bruke denne antagelsen:
\[ \begin{aligned} \sum_{i=1}^{k+1}i &= \sum_{i=1}^{k}i + (k+1) \\ &= \frac{k(k+1)}{2} + (k+1) \\ &= \frac{(k+1)(k+2)}{2} \end{aligned} \]
Her ser vi altså at dersom formelen er riktig for <math>n=k</math>, så vil formelen være riktig for <math>n=k+1</math>. Dette kompletterer induksjonsbeviset.
Denne "malen" for induksjonsbevis vil i prinsippet gjelde for alle problemer, dog vil det kunne oppstå ulike vanskeligheter for de spesifikke variasjonene, men disse er av "algebraisk" karakter. For å bli fortrolig med induksjon er man nødt til å regne gjennom en del eksempler.
Eksempel 1:
La oss se litt nærmere på eksemplet over, denne gangen uten bruk av summetegn:
\[ 1 + 2 + 3 + \ldots + \ n = \frac{n (n+1)}{2} \]
Tallet n skal være et positivt helt tall. Først undersøker man induksjonsgrunnlaget: Når n = 1 blir høyre side lik venstre side.I induksjonstrinnet antar vi først at formelen er riktig for n = k:
\[ 1 + 2 + 3 + \ldots + k = \frac{k (k+1)}{2} \]
Deretter undersøker vi summen for n = k + 1, ved å bruke antagelsen:
\[ \begin{aligned} 1 + 2 + 3 + \ldots + k + (k+1) &= \frac{k (k+1)}{2} + (k+1) \\ &=(k+1) ( \frac{k}{2} + 1) \\ &= \frac{(k+1)(k + 2)}{2} \end{aligned} \]
Vi ser at den siste linjen er høyresiden i formelen når n = k + 1. Altså er beviset fullført.
Eksempel 2:
Bevis formelen
\[ 1^2 + 2^2 + 3^2 +.....+ n^2 = \frac{n(n+1)(2n+1)}{6} \qquad n \in \mathbb{N} \]
Man finner først om induksjonsgrunnlaget er sant. Når n = 1 er venstre side lik <math> 1^2 = 1,</math> og høyre side er <math> \frac{1 \cdot 2 \cdot 3}{6} = 1.</math> Induksjonsgrunnlaget er dermed sant, begge sider er lik 1 for n=1.
I induksjonstrinnet antar vi først at formelen er riktig for n = k:
\[ 1^2 + 2^2 + 3^2 + \ldots + k^2 = \frac{k(k+1)(2k+1)}{6} \]
Så undersøker vi summen for n = k + 1 ved å bruke antagelsen:
\[ \begin{aligned} 1^2 + 2^2 + 3^2 +.....+ k^2 + (k+1)^2 &= \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \\ &= (k+1) [ \frac{k(2k+1)}{6} + (k+1) ] \\ &= (k+1) \frac{k[2k+1 + 6(k+1)]}{6} \\ &= \frac{(k+1)[2k^2+7k+6]}{6} \\ &= \frac{(k+1)[2(k+2)(k + \frac{3}{2})]}{6} \\ &= \frac{(k+1)(k+2)(2k + 3)}{6} \\ \end{aligned} \]
Den siste linjen er høyresiden i formelen når n = k + 1.
Q.E.D. (quod erat demonstrandum)
Eksempel 3:
Bevis derivasjonsregelen $(x^n)' = nx^{n-1}.$
I induksjonsgrunnlaget viser vi først at formelen gjelder for n = 1:
- Høyre side: $n \cdot x^{n-1} = 1 \cdot x^0 =1$
- Venstre side $(x^1)'= x' =1$
Induksjonsgrunnlaget er sann: Linjen y = x har stigningstall 1.
I induksjonstrinnet antar vi som vanlig at formelen er riktig for n = k:
\[ (x^k)' = kx^{k-1} \]
Vi viser så at formelen holder for n = k + 1, ved å bruke antagelsen sammen med regelen for derivering av et produkt:
\[ \begin{aligned} (x^{k+1})' &= (x \cdot x^k)' \\ &= x^k + x \cdot k \cdot x^{k-1} \\ &= x^k + kx^k \\ &= (1+k)x^k \end{aligned} \]
Q.E.D.
Eksempel 4:
Bevis at $n^3-4n+6$ er delelig på 3 når n er et ikke-negativt heltall.
1. Induksjonsgrunnlag: n=0 gir $n^3-4n+6 = 6$, som er delelig på 3.
2. Induksjonstrinnet: Anta at $n^3-4n+6$ er delelig på 3 når n = k. Med n = k + 1 får vi
\[ \begin{aligned} (k+1)^3 -4(k+1) + 6 &= (k+1)(k^2 + 2k + 1)- (4k + 4) + 6 \\ &= (k^3 + 2k^2 + k + k^2 + 2k + 1) - 4k + 2 \\ &= (k^3 -4k + 6) + 3(k^2 + k - 1) \end{aligned} \]
Den første parantesen er delelig på 3, i følge antagelsen for n = k. Den andre inneholder faktoren 3. Sammen gir dette at hele uttrykket er delelig på 3.