Induktion

Induktion er en metode til at bevise udsagn, der gælder for alle naturlige tal.

Ideen er at vise, at hvis et udsagn gælder for det første tal, og hvis det gælder for et vilkårligt tal \( \large k \), så må det også gælde for \( \large k+1 \). På den måde viser man, at udsagnet holder for alle \( \large n \).

 

Induktion fungerer som en domino-række: Hvis den første brik falder (basis-trinnet), og hver brik får den næste til at falde (induktionsskridtet), så falder alle brikker i rækken.

 

Fremgangsmåde

Et induktionsbevis består normalt af tre trin:

 

1. Basis: Vis at udsagnet gælder for det første naturlige tal, typisk \( \large n=1 \).
2. Induktionshypotese: Antag, at udsagnet gælder for et vilkårligt \( \large n=k \).
3. Induktionsskridt: Brug antagelsen til at vise, at udsagnet også gælder for \( \large n=k+1 \).

 

 

Eksempel 1

Vi vil bevise ved induktion, at summen af de første \( \large n \) naturlige tal er

 

$$ \large 1 + 2 + \cdots + n = \frac{n(n+1)}{2} $$

 

Basis:

 

For \( \large n=1 \) får vi \( \large 1 = \frac{1 \cdot (1+1)}{2} = 1 \). Udsagnet er sandt.

 

Induktionshypotese:

 

Antag, at udsagnet gælder for \( \large n=k \):

 

$$ \large 1 + 2 + \cdots + k = \frac{k(k+1)}{2} $$

 

Induktionsskridt:

 

For \( \large n=k+1 \) får vi:

 

$$ \large 1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) $$

 

$$ \large = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2} $$

 

Som er den samme formel med \( \large n=k+1 \). Dermed er udsagnet bevist for alle \( \large n \).

 

 

Eksempel 2

Vi vil bevise ved induktion, at \( \large 5^n - 2^n \) altid er deleligt med 3 for alle \( \large n \in \mathbb{N} \).

 

Basis:

 

For \( \large n=1 \) får vi \( \large 5^1 - 2^1 = 3 \), som er deleligt med 3.

 

Induktionshypotese:

 

Antag, at udsagnet gælder for \( \large n=k \):

 

$$ \large 5^k - 2^k = 3m $$

 

for et eller andet helt tal \( \large m \).

 

Induktionsskridt:

 

For \( \large n=k+1 \) starter vi med at omskrive potenserne:

 

$$ \large 5^{k+1} - 2^{k+1} = 5 \cdot 5^k - 2 \cdot 2^k $$

 

Nu vil vi gerne samle et led med \( \large (5^k - 2^k) \). Derfor skriver vi \( \large -2 \cdot 2^k \) om som \( \large -5 \cdot 2^k + 3 \cdot 2^k \). Så får vi:

 

$$ \large 5 \cdot 5^k - 2 \cdot 2^k = 5 \cdot 5^k - 5 \cdot 2^k + 3 \cdot 2^k $$

 

Nu kan de to første led samles i en parentes:

 

$$ \large = (5^k - 2^k)\cdot 5 + 3 \cdot 2^k $$

 

Ved induktionshypotesen er \( \large 5^k - 2^k \) deleligt med 3, og \( \large 3 \cdot 2^k \) er tydeligvis også deleligt med 3. Dermed er hele udtrykket deleligt med 3, og udsagnet er vist for \( \large n=k+1 \).

 

 

Induktionsbeviser er et centralt værktøj i matematikken. De bruges til at bevise formler, egenskaber ved talrækker, divisibilitet og meget mere.

Metoden viser, hvordan en påstand kan holde for uendeligt mange tal ved at forbinde hvert trin i rækken logisk med det næste.