Induksjonsbevis

[Markus]

Hei, jeg synes det med induksjonsbevis fortsatt er litt rart.

Ønsker å bevise at $3 \mid n^3-n, \enspace \forall n \in \mathbb{N}$

Det finnes jo selvfølgelig en måte uten induksjonsbevis; faktorisere til $(n-1)n(n+1)$, som er trepåfølgende heltall som må være delelig på 3, men det er altså ikke denne metoden jeg er ute etter.

Med induksjon tenker jeg sånn her:
Basistilfellet
For $n=1$ har vi $1^3-1 = 0$ og $3 \mid 0 \enspace \enspace \checkmark$

Induksjonstrinnet
Vi antar at påstanden $P(n)$ holder for $P(k)$, altså at $3 \mid k^3-k$.
Vi ønsker å vise at $P(k+1)$ holder.

$(k+1)^3-(k+1)=k^3+2k^2+k+k^2+2k+1-k-1$

$(k+1)^3-(k+1)=(k^3-k) + 3k^2+3k$

$(k+1)^3-(k+1)=(k^3-k)+3(k^2+k)$

Det er lett å se at det siste leddet er delelig på $3$, da $3$ er en faktor, men det første leddet er jo bare det vi antok. Hvorfor vil det også være delelig på $3$?
Akkurat denne tankegangen går igjen i alle induksjobevis, jeg forstår ikke helt hvorfor vi bare kan anta at $P(n)$ stemmer. Noen som kunne ha forklart dette?

[Gustav]

Du kan jo anta det du vil. Det er vel kanskje dette som skiller matematikk som teoretisk fagfelt, fra den erfaringsbaserte, praktiske og konkrete måten folk ellers er så vant til, og som gjør at mange aldri skjønner eller lærer seg å sette pris på matematikken og dens indre skjønnhet.

Induksjonsbeviser er som dominobrikker som faller en etter en. I første steg så igangssetter du dominoeffekten. I andre induksjonssteg beviser du at brikken som kommer etter den som faller, også nødvendigvis må falle.

[Markus]

Det var en flott analogi Gustav!

Så med andre ord; hvis påstanden stemmer for $P(k+1)$, så må det også stemme for $P(k)$?

[alund]

At hvis påstanden [tex]P(k)[/tex] stemmer, må også [tex]P(k+1)[/tex] stemme, er det vi prøver å bevise.
Du har vist at uttrykket [tex](k+1)^3-(k+1)=(k^3-k)+3(k^2+k)[/tex], og siden du antar at utsagnet [tex]P(k):\: 3|k^3-k[/tex] er sant, har du vist at den antagelsen medfører at [tex]P(k+1)[/tex] må være sant. [tex]P(k+1)[/tex] er da sant hvis [tex]P(k)[/tex] er det. For å stole på at [tex]P(k)[/tex] kan være sant, beviser du først at det er sant for basistilfellet [tex]n=1[/tex]. Da har du bevist at [tex]P(1+1)=P(2)[/tex] er sant, som medfører riktighet i [tex]P(3),P(4),P(5),...[/tex].

[Markus]

At hvis påstanden [tex]P(k)[/tex] stemmer, må også [tex]P(k+1)[/tex] stemme, er det vi prøver å bevise.
Du har vist at uttrykket [tex](k+1)^3-(k+1)=(k^3-k)+3(k^2+k)[/tex], og siden du antar at utsagnet [tex]P(k):\: 3|k^3-k[/tex] er sant, har du vist at den antagelsen medfører at [tex]P(k+1)[/tex] må være sant. [tex]P(k+1)[/tex] er da sant hvis [tex]P(k)[/tex] er det. For å stole på at [tex]P(k)[/tex] kan være sant, beviser du først at det er sant for basistilfellet [tex]n=1[/tex]. Da har du bevist at [tex]P(1+1)=P(2)[/tex] er sant, som medfører riktighet i [tex]P(3),P(4),P(5),...[/tex].

Takk for grundig gjennomgang. Det klarte opp i de spørsmålene jeg hadde.