Induktion, rekursion och bevis

Ett induktionsbevis har två uppgifter: visa ett första giltigt fall och visa att varje giltigt fall leder till nästa. Induktionsantagandet får användas för det fixerade steget, men inte för det steg som ännu ska bevisas. Vid stark induktion får samtliga tidigare fall användas. Detta passar till exempel faktorisering där ett tal delas i flera mindre tal.

$$P(n_0)\ \land\ \bigl(\forall n\ge n_0:\ P(n)\Rightarrow P(n+1)\bigr)\Rightarrow\forall n\ge n_0:\ P(n)$$

Basfallet är att det första udda talet är ett. Antag att summan av de första n udda talen är n i kvadrat. Nästa term är två gånger n plus ett. När den läggs till bildas precis utvecklingen av nästa kvadrat. Slutsatsen gäller därför för alla positiva heltal.

$$\sum_{k=1}^{n+1}(2k-1)=n^2+2n+1=(n+1)^2$$

En rekursionsregel beskriver nya värden med hjälp av tidigare värden. Fibonacci-regeln använder två tidigare termer och behöver därför två startvärden. När ett bevis använder två föregående steg måste även de första fallen täckas. För summor med en tom indexmängd är summan noll; det kan göra noll till det naturliga basfallet. Vid ett motsägelsebevis antar man negationen av slutsatsen och härleder ett påstående som strider mot givna villkor.

$$F_0=0,\quad F_1=1,\quad F_{n+2}=F_{n+1}+F_n$$