Beviser med rekursion og induktion

Når man arbejder med rekursive definitioner og algoritmer, er det vigtigt at kunne bevise at de faktisk gør det rigtige. Den naturlige metode til dette er matematisk induktion. Induktion ligner rekursion: man starter med et basis-trin og viser derefter at hvis udsagnet gælder for et trin, gælder det også for det næste.

 

 

Eksempel 1: Fakultet

Vi vil bevise at den rekursive definition af fakultet svarer til den sædvanlige produktformel:

 

$$ \large n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n, \quad n \geq 1 $$

 

Basis

 

For \( \large n = 1 \):

 

$$ \large 1! = 1 \quad \text{gælder} $$

 

Induktionsskridt

 

Antag at påstanden gælder for et bestemt \( \large n \), dvs.

 

$$ \large n! = 1 \cdot 2 \cdot \ldots \cdot n $$

 

Så får vi for \( \large n+1 \):

 

$$ \large (n+1)! = (n+1) \cdot n! $$

 

Ved induktionsantagelsen kan vi erstatte \( \large n! \):

 

$$ \large (n+1)! = (n+1) \cdot (1 \cdot 2 \cdot \ldots \cdot n) $$

 

Dermed får vi præcis produktet op til \( \large n+1 \). Påstanden gælder altså for alle \( \large n \).

 

 

Eksempel 2: Fibonacci

Fibonacci-følgen er defineret ved

 

$$ \large F_{0} = 0, \quad F_{1} = 1, \quad F_{n} = F_{n-1} + F_{n-2} \;\; (n \geq 2) $$

 

En kendt formel siger at summen af de første \( \large n \) Fibonacci-tal er:

 

$$ \large F_{0} + F_{1} + \ldots + F_{n} = F_{n+2} - 1 $$

 

Basis

For \( \large n = 0 \) har vi til venstre blot summen \( \large F_{0} = 0 \).

På højre side står \( \large F_{2} - 1 = 1 - 1 = 0 \).

Begge sider giver samme resultat, så påstanden gælder i basis-tilfældet.

 

Induktionsskridt

Antag at påstanden gælder for et bestemt \( \large n \):

 

$$ \large F_{0} + F_{1} + \ldots + F_{n} = F_{n+2} - 1 $$

 

Vi viser det for \( \large n+1 \):

 

$$ \large F_{0} + F_{1} + \ldots + F_{n} + F_{n+1} $$

$$ \large = (F_{n+2} - 1) + F_{n+1} \quad \text{(ved induktionsantagelsen)} $$

$$ \large = F_{n+1} + F_{n+2} - 1 $$

$$ \large = F_{n+3} - 1 $$

 

Dermed gælder påstanden også for \( \large n+1 \). Ved induktion gælder formlen for alle \( \large n \).

 

 

Eksempel 3: Korrekthed af en rekursiv algoritme

Vi så tidligere algoritmen der finder maksimum i en liste:

 

function max(list):
    if list has length 1:
        return list[0]            // basis
    else:
        m = max(rest of list)     // rekursivt skridt
        return the larger of list[0] and m

 

Vi vil bevise at algoritmen altid returnerer det største element i listen.

 

Basis

Hvis listen har længde 1, returnerer algoritmen det eneste element. Det er korrekt, da et enkelt element selvfølgelig er maksimum.

 

Induktionsskridt

Antag at algoritmen virker korrekt for alle lister med længde \( \large n \). Vi skal vise at den så også virker for en liste med længde \( \large n+1 \).

 

Lad listen være \( \large [x_0, x_1, \ldots, x_n] \). Algoritmen kalder sig selv på underlisten \( \large [x_1, \ldots, x_n] \), som har længde \( \large n \). Ved induktionsantagelsen returnerer dette kald korrekt maksimum for underlisten.

 

Til sidst sammenligner algoritmen dette maksimum med det første element \( \large x_0 \). Dermed returneres det største af alle elementer \( \large x_0, x_1, \ldots, x_n \), altså maksimum for hele listen.

 

Konklusion

Ved induktion gælder at algoritmen max altid returnerer det største element i en liste uanset længden.

 

 

Opsummering

Induktion er den naturlige metode til at bevise korrekthed af rekursive definitioner. Man viser at basis stemmer, og at hvis påstanden gælder i ét trin, gælder den også i det næste. Dermed er hele den uendelige konstruktion dækket. Dette gør induktion til et fundamentalt værktøj i arbejdet med rekursion.