1. Matematisk induksjon: basistilfelle og induksjonssteg

For å bevise at en påstand \(P(n)\) gjelder for alle \(n\ge n_0\) (ofte \(n_0=0\), siden \(\mathbb{N}\) inkluderer 0), gjør du to ting: viser basistilfellet \(P(n_0)\), og viser induksjonssteget \(P(k)\Rightarrow P(k+1)\). Antakelsen \(P(k)\) inne i steget heter induksjonshypotesen (IH). Begge deler er nødvendige: steget alene kan være gyldig uten at noen \(P(n)\) er sann, og basis alene sier ingenting om de uendelig mange neste tilfellene.

Mal for induksjonsbevis:

1) Basis: Vis \(P(n_0)\) eksplisitt.
2) IH: Anta \(P(k)\) for et vilkårlig \(k\ge n_0\).
3) Steg: Bruk IH til å utlede \(P(k+1)\).
4) Konklusjon: Etter induksjonsprinsippet gjelder \(P(n)\) for alle \(n\ge n_0\). \(\blacksquare\)

Eksempel: Bevis at \(\sum_{i=1}^{n} i=\frac{n(n+1)}{2}\) for alle \(n\ge1\).

Basis \(n=1\): venstre \(=1\), høyre \(=\frac{1\cdot2}{2}=1\). OK.

IH: anta \(\sum_{i=1}^{k} i=\frac{k(k+1)}{2}\).

Steg: \(\sum_{i=1}^{k+1} i=\left(\sum_{i=1}^{k} i\right)+(k+1)\)

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

\(=\frac{(k+1)(k+2)}{2}\), som er formelen for \(k+1\). \(\blacksquare\)

2. Sterk induksjon med flere basistilfeller

I sterk induksjon styrker du hypotesen: du antar \(P(j)\) for alle \(j\) med \(n_0\le j\le k\), ikke bare \(P(k)\). Dette er nødvendig når \(P(k+1)\) avhenger av flere tidligere ledd, eller av vilkårlige mindre tall (som ved primtallsfaktorisering). Antall basistilfeller bestemmes av hvor langt tilbake steget refererer: en rekurrens av dybde \(d\) (som Tribonacci, \(d=3\)) krever \(d\) basistilfeller, fordi steget først kan anvendes når alle refererte ledd er definert.

Når trenger du sterk induksjon / flere basistilfeller?

Steget bruker bare \(P(k)\) og ett tidligere ledd \(\Rightarrow\) svak induksjon, ett basistilfelle holder ofte.
Steget bruker \(P(k),P(k-1),\dots\) eller vilkårlige mindre tall \(\Rightarrow\) sterk induksjon; ha nok basistilfeller til at steget alltid «når bakover» til noe bevist.

Eksempel: Et postverk har kun 4- og 5-øres frimerker. Vis at ethvert porto \(\ge12\) øre kan settes sammen.

Basistilfeller: \(12=4{+}4{+}4\), \(13=4{+}4{+}5\), \(14=4{+}5{+}5\), \(15=5{+}5{+}5\).

IH: anta at alle beløp \(j\) med \(12\le j\le k\) kan lages, der \(k\ge15\).

Steg \(n=k+1\ge16\): da er \(n-4\ge12\), så \(n-4\) kan lages (IH).

Legg til ett 4-frimerke: \((n-4)+4=n\). \(\blacksquare\)

Fire basistilfeller fordi steget reduserer med 4 (vi må dekke 12,13,14,15).

3. Rekursivt definerte følger (Fibonacci/Tribonacci-type)

En rekurrens definerer ledd ut fra tidligere ledd pluss startverdier. Fibonacci: \(F_1=F_2=1\), \(F_n=F_{n-1}+F_{n-2}\) gir \(1,1,2,3,5,8,13,\dots\). Tribonacci: \(T_0=0,\,T_1=T_2=1\), \(T_n=T_{n-1}+T_{n-2}+T_{n-3}\) gir \(0,1,1,2,4,7,13,\dots\). Slike følger bevises ofte med sterk induksjon, og man kan utlede nyttige identiteter (f.eks. \(\sum_{i=1}^{n}F_i=F_{n+2}-1\)).

4. Bevis av lukket form for rekurrens ved induksjon

Strategien er gjett og bevis: beregn de første leddene, gjett en lukket form \(a_n=f(n)\), og bekreft ved induksjon. For lineære homogene rekurrenser med konstante koeffisienter bruker man karakteristisk ligning til å finne kandidatform, og verifiserer deretter mot startverdiene.

Eksempel: Løs \(a_0=2,\,a_1=5,\,a_n=5a_{n-1}-6a_{n-2}\).

Karakteristisk ligning: \(x^2-5x+6=0\Rightarrow(x-2)(x-3)=0\), røtter \(2,3\).

Ansats: \(a_n=A\cdot2^n+B\cdot3^n\).

Startverdier: \(A+B=2\) og \(2A+3B=5\Rightarrow B=1,\,A=1\).

Lukket form: \(a_n=2^n+3^n\). Sjekk \(a_2=4+9=13=5\cdot5-6\cdot2\). \(\blacksquare\)

5. Strukturell induksjon på strenger og rekursivt definerte mengder

Når objekter er rekursivt definert (strenger via \(\varepsilon\) og symbolpåheng, mengder via grunnelementer og konstruksjonsregler, trær via blader og deltrær), beviser man egenskaper ved strukturell induksjon: vis påstanden for grunnelementene (basis), og vis at hver konstruksjonsregel bevarer den (steg). Sentrale eksempler: \(|uv|=|u|+|v|\) og \((uv)^R=v^R u^R\), bevist ved induksjon på oppbyggingen av den andre strengen.

Eksempel: Bevis \((uv)^R=v^R u^R\) ved strukturell induksjon på \(v\). Reversering: \(\varepsilon^R=\varepsilon\), \((wx)^R=x\,w^R\); konkatenering: \(u\cdot(wx)=(u\cdot w)x\).

Basis \(v=\varepsilon\): \((u\varepsilon)^R=u^R\) og \(\varepsilon^R u^R=\varepsilon u^R=u^R\). OK.

IH: anta \((uw)^R=w^R u^R\) for en streng \(w\).

Steg \(v=wx\): \((u\,wx)^R=((uw)x)^R=x\,(uw)^R\)

\(\overset{IH}{=}x\,w^R u^R=(wx)^R u^R=v^R u^R\). \(\blacksquare\)

Studieguide: Induksjon og rekursjon

Studieguide: Induksjon og rekursjon