Sliter litt med induksjons-bevis

[Sir Zu Zwat]

Induksjon er ikke akkurat min sterkeste side. Denne gangen slal jeg bevise at 3 går opp i 5^n - 2^n for alle positive heltall n. Første trinn er jo lett. Sette n til 1 og se om det stemmer. Det er verre når det begynner med k og (k + 1).

 

Noen som kan hjelpe litt?

[Jaffe]

For å fortsette nå, antar du at påstanden gjelder for et tall n = k. Det vil si at  der s er et tilfeldig heltall.

 

Så ser du på uttrykket for n = k + 1. Da får du: . Ut fra potensreglene får vi nå

 

 

Nå kan vi gjøre et lite triks. Vi skriver som , og som :

 

 

Stokker vi om litt har vi at dette er det samme som

 

Men er jo som vi antok i sted, det samme som 3s. Da kan vi bytte ut med det:

 

 

Vi ser nå at 3 også er faktor i uttrykket for n = k+1. Dermed har vi vist at dersom uttrykket er delelig på 3 for n = k, så er det også det for n = k +1. Og siden du har vist at det er delelig på 3 for n = 1, så er det også det for 2, etter det vi nettopp har vist. Og da er det også sant for n = 3 og så videre.

 

edit: omformulerte beviset noe, tok bort et unødvendig steg der man ser på differansen mellom uttrykket for n = k og n = k+1. Dette kan man også gjøre, men det er ikke nødvendig.

Endret 20. oktober 2009 av Jaffe

[kringon]

Vedder en babb på at trådstarter tar Diskret Matematikk på HIO

[Sir Zu Zwat]

Vedder en babb på at du gjør det samme.