Første øving for MA1301-Tallteori, 30/8-2005

Oppgavene hentes fra læreboken og fra tidligere eksamensoppgaver. I tillegg er det noen ekstraoppgaver som er skrevet helt ut.

Fra boken, Problems 1.1 side 6-8: 1,3,9,11,14.

Eksamen 26/5-2003: Oppgave 5a): Vis ved induksjon at hvert positivt heltall $N$ kan skrives på formen

$$N=a_m100^m+a_{m-1}100^{m-1}+\cdots + a_1100+a_0$$

hvor koeffisientene $a_i$ er heltall i intervallet $[0,99]$.

Ekstraoppgaver, tema er hva som kan gå galt med induksjon.

1) Hva er galt med følgende resonnement?

Påstand: Alle barn har samme øyenfarge.
Bevis: Vi viser dette med induksjon på antall barn, $n$. For $n=1$ er utsagnet trivielt, ett barn har en gitt øyenfarge. Anta resultatet holder for alle samlinger av $n=k-1$ barn, vi vil vise at det er sant for $n=k$ barn. Så gitt en samling av $k$ barn, still dem opp på rekke; per induksjon har de første $k-1$ av barna samme øyenfarge, og også de siste $k-1$. Men da vil de $k-2$ barna i midten ha samme øyenfarge både som de $k-1$ første og som de $k-1$ siste! Følgelig har alle de $k$ barna samme øyenfarge, og påstanden er bevist med matematisk induksjon.

2) Det er viktig å sjekke startbetingelsen! Vis at induksjonssteget holder for følgende påstand (altså: om det er sant for et heltall $k-1$, vil det også være sant for $k$), men siden utsagnet ikke er riktig for noe heltall, er ikke dette nok!

Påstand: $1+2+3+\cdots+(n-1)+n=\frac{n^2+n+1}{2}$

Jon Eivind Vatne