Induksjon

Ser på en egenskap $P$ definert på $\mathbb{N}$. Dvs at for hver $n\in \mathbb{N}$ er $P(n)$ et utsagn. $P$ anvendes på de naturlige tall.

Konvensjon at: hvis jeg skriver $P(n)$ betyr det som oftest at $P(n)$ er et sant utsagn.

Eks: $P(n)$ er at $2^n\ge 1000$
$P(0)$ er usant.
$P(10)$ er sant
bevise at det sant for $n>10$?
neida, vi bare demonstrere hva et utsagn er.

Hva vil vi bevise for alle tall?

$P(n)$ er $1+q+\cdots +q^n=\frac{1-q^{n+1}}{1-q}$ $q{\ne }_1$
Geometrisk:)

$1+2+3+\cdots +n=n\ast \frac{n+1}{2}$
Aritmetisk:)

Induksjonsbevis:

1. $P(0)$ er sant
2. Og $\forall n\in \mathbb{N}$ (hvis$P(n)$ så $P(n+1)$)
   Så kan vi konkludere at for alle $m\in \mathbb{N}$ har vi $P(n)$

$P(n)$ Induksjonshypotesen
Grunntrinn, induksjonstrinn.

Eksempel

$P(0)$ er utsagnet $1=\frac{1-q}{1-q}$
Har sjekket at grunntrinnet stemmer.

Induksjonstrinnet: La $n\in \mathbb{N}$ (VILKÅRLIG TALL:)
Vi antar at $P(n)$ og vil utlede $P(n+1)$
Vi har altså at
$1+q+\cdots +q^n=\frac{1-q^{n+1}}{1-q}$
FVI får $1+q+\cdots +q^n+q^{n+1}=\frac{1-q^{n+1}}{1-q}+q^{n+1}$
også pittelitt algebra:)

“helt vanlig at ting plutselig går opp på en litt sånn mirakulær måte”
“mirakelet er jo at formelen i utgangspunktet er noe vi er overbevist om er sann”

… fyll innn fra skrivebok…

Regneregler for summetegn

$b\left({\sum }_{k=m}^n{a}_k\right)={\sum }_{}$ b ganget inn
sum av ak fra k til n og fra n+1 til p = sum fra k til p

Produkt av to summer

Kan skrives som dobbel sum av produkter.
Tegn opp rutenett… fyll ut. Distributivitet.

Visualiser… gymnastikk.

neste emne Kombinatorikk og binomialformelen