Kalkulus
"Av alt vås er vitenskapens det verste, 
fordi det er så fordømt logisk og gjennomtenkt." 
-Louis-Ferdinand Céline i 'Reisen til nattens ende'.

1. Naturlige tall

1.1 Regneregler for summer

(Se notasjonen)

(i)

(n=k,m) an + (n=k,m) bn = (n=k,m) (an + bn)

(ii) Konstanter kan settes utenfor

(n=k,m) c * an = c * (n=k,m)

(iii)

(n=k,m) an + (n=m+1,l) an = (n=k,l) an
 
 

Bevis for (ii)

(n=k,m) c * an = (c * ak + c * ak+1 + c * ak+2 + . . . + c * am)
= c (ak + ak+1 + ak+2 + . . . + am)
= c * (n=k,m) an
 

1.1.2 Bytte av summasjonsindeks

Har to summer
(1)
(k=-3,11)  (-1)^k * x^(k+3)
(2)
(k=0,14) (-1)^(k+1) * x^k

Skrevet ut blir begge
-1 + x - x^2 + x^3 . . . -x^14

Skal vise at (1) og (2) er like

Omforme (1)
i = k+3, k = i -3

Starter på k = -3, da er i = 0
Slutter på k = 11, da er i = 14

(i=0,14) (-1)^(i-3) * x^i

Og siden (-1)^(i-3) = (-1)^(i-3) * (-1)^4 = (-1)^(i+1)
tilsvarer ovennevnte
(i=0,14)(-1)^(i+1) * x^i
= (2)
 

1.2 Induksjonsbevis

Vi har ofte behov for å regne ut følgende sum:
(i=1,n) i

Det viser seg at
(i=1,n) i = [n(n+1)]/2

Vi tester på n=1, n=2, n=3, n=4
(i=1,1) i = 1*2/2 = 1
(i=1,2) i = 2*3/2 = 3
(i=1,3) i = [(i=1,2) i ] + 3 = 6, tilsvarer 3*3/2 = 6
(i=1,4) i =[(i=1,3) i] + 4 = 10, tilsvarer 4*2/5 = 10

Anta at vi fortsetter og finner at formelen stemmer for n=k
(i=1,k) i = [k(k+1)]/2

Stemmer det for n = k+1?

(i=1,k+1) = [(i=1,k) i] + (k + 1) = [k(k+1)]/1 + (k+1)
=(k+1)(k/2 + 1)
=(k+1)(k/2 + 2/2)
=[(k+1)(k+2)]/2

{ Hvis n=k+1, gir formelen [n(n+1)]/2 -> [(k+1)(k+2)]/2 }
Konklusjon: Hvis formelen (i=1,n) i = [n(n+1)]/2
stemmer for n=k, da stemmer den også for n=k+1,
uansett hva k er (k >= 1)
Siden den stemmer for n=1, må den stemme for alle n.

Beviset må inneholde det første tallet med tall (f.eks n=1), tilsvarende base case i rekursive programmer.
 

1.2.1 Generelt induksjonsbevis (DeMorgan)

Algoritme for generelt induksjonsbevis:

Vi har mange utsagn Pn som vi skal vise er riktige for n = 1,2,3,...

Ex. Pn = (i=1,n) i = [n(n+1)]/2

Vi gjør følgende
(1) Sjekk at P1 er riktig.
(2) Anta at Pk er riktig og bruk dette til å vise at Pk+1 er riktig.

Hvis dette går bra, så er Pn riktig for alle naturlige tall n.