Bevis och induktion

Ett bevis är en kedja av steg där varje steg följer av det förra, och slutsatsen därför måste vara sann.

Fyra bevisformer du behöver känna igen:

Form	Idé	Används till
Direkt	anta förutsättningen, räkna fram slutsatsen	de flesta
Motexempel	hitta ett enda fall där påståendet är falskt	motbevisa
Motsägelse	anta motsatsen, härled något orimligt	«det finns inget …»
Induktion	visa första fallet, visa att varje fall ger nästa	påståenden om alla n

Induktion är dominobrickorna: visa att första brickan faller, och att varje bricka fäller nästa. Då faller alla.

Varför en programmerare bryr sig: ett induktionsbevis och en rekursiv funktion har exakt samma struktur. Basfallet i koden är basfallet i beviset; det rekursiva anropet är induktionssteget. Kan du skriva den ena kan du läsa den andra.

Induktionsbevis i tre steg. Påstående: $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$.

1. Basfall ($n = 1$): vänsterledet är 1, högerledet $\frac{1\cdot2}{2} = 1$. ✓

2. Induktionsantagande: anta att formeln gäller för något $n = k$, alltså $1 + \dots + k = \frac{k(k+1)}{2}$.

3. Induktionssteg: visa att den då gäller för $k+1$.

$1 + \dots + k + (k+1) = \underbrace{\frac{k(k+1)}{2}}_{\text{antagandet}} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$

Det sista uttrycket är precis formeln med $k+1$ insatt. ∎

Motsägelsebevis. Påstående: $\sqrt{2}$ är irrationellt.

Anta motsatsen: $\sqrt{2} = p/q$ i lägsta termer. Då är $2q^2 = p^2$, så $p^2$ är jämnt, alltså är $p$ jämnt, säg $p = 2m$. Då är $2q^2 = 4m^2$, alltså $q^2 = 2m^2$, så även $q$ är jämnt. Men då hade bråket inte varit i lägsta termer. Motsägelse. ∎

Ett motexempel räcker för att falsifiera. «Alla primtal är udda» faller på $2$. Det är samma logik som negation av kvantorer: motsatsen till $\forall x\,P(x)$ är $\exists x\,\neg P(x)$.

Vanliga fel i induktionsbevis:

Fel	Varför det är fel
Glömma basfallet	dominobrickorna faller aldrig omkull
Anta det man ska visa	cirkelbevis
Anta för alla $n$ i stället för ett	då har man antagit slutsatsen
Verifiera några fall och kalla det bevis	tre fall är inte alla fall

# Induktion och rekursion har samma struktur
def summa(n):
    if n == 1:            # basfall — samma som bevisets basfall
        return 1
    return summa(n - 1) + n     # induktionssteg: antag att n-1 stämmer

def formel(n):
    return n * (n + 1) // 2

assert all(summa(n) == formel(n) for n in range(1, 500))
print("stämmer för n = 1..499")

# Men: kontroll är inte bevis.
# Påstående: n² + n + 41 är alltid ett primtal.
def ar_primtal(x):
    return x > 1 and all(x % d for d in range(2, int(x ** 0.5) + 1))

print(all(ar_primtal(n**2 + n + 41) for n in range(40)))     # True  — 40 fall stämmer!
print(ar_primtal(40**2 + 40 + 41))                            # False — motexempel
print(40**2 + 40 + 41, "=", 41 * 41)                          # 1681 = 41 · 41

# Leta motexempel systematiskt — bra vana innan man försöker bevisa
def forsta_motexempel(pastaende, hogst=10_000):
    return next((n for n in range(1, hogst) if not pastaende(n)), None)

print(forsta_motexempel(lambda n: ar_primtal(n**2 + n + 41)))   # 40

Exemplet med $n^2 + n + 41$ är klassiskt just för att det stämmer för de fyrtio första talen. Att testa är utmärkt för att hitta fel, men det kan aldrig visa att inget fel finns — vilket är hela skillnaden mellan testning och bevis, i programmering likaväl som i matematik.