Induksjonsbevis

[luringen]

Hei.

Driver å jobber med noen oppgaver om induksjonsbevis. Sliter litt med to av oppgavene. Jeg har løsningsforslag, men forstår ikke helt alt som blir gjort.

Oppgavene:


I oppgave c), hvorfor blir (3n[sup]2[/sup] − 3n) lagt til uttrykket? Holder det ikke å stoppe når man har uttrykket: ((n[sup]3 [/sup]−n)−3n[sup]2[/sup] +3n), siden (n[sup]3 [/sup]−n) har vi antatt er delelig med 3, og (−3n[sup]2[/sup] +3n) ser vi er delelig med 3.



I oppgave d) skjønner jeg ikke hva som blir gjort her: "Ved ̊a gange med 5 og legge til 4 f ̊ar vi at"..

[Audunss]

I oppgave c), hvorfor blir (3n[sup]2[/sup] − 3n) lagt til uttrykket? Holder det ikke å stoppe når man har uttrykket: ((n[sup]3 [/sup]−n)−3n[sup]2[/sup] +3n), siden (n[sup]3 [/sup]−n) har vi antatt er delelig med 3, og (−3n[sup]2[/sup] +3n) ser vi er delelig med 3.



I oppgave d) skjønner jeg ikke hva som blir gjort her: "Ved ̊a gange med 5 og legge til 4 f ̊ar vi at"..

På c) oppgaven så legger de til det de legger til fordi de starter i n-1, så de har ikke antatt at n^3-n er delelig med 3, det er hva de skal vise.

På d) oppgaven så gjør de disse forandringene på uttrykket fordi de ikke gjør noe om du får en rest når du deler på 4, og når disse forandringene blir gjort får de et uttryk som viser at 5^n-1 er delelig med 4.

Kan bise et annet bevis på oppgaven der vi begynner med n=k, og viser det for k+1.

Anter at 5^k-1 er delelig med 4, skal vise at 5^(k+1)-1 er delelig med 4.

5^(k+1)-1=5*5^k-1-4+4=5*5^k-5+4=5*(5^k-1)+4

Siden 4 er delelig på 4, og vi antar 5^k-1 er delelig på 4, er 5^(k+1)-1 delelig på 4

[chrypton1]

Kan vise deg hvordan jeg ville ha gjort oppgave c)

1. Anta [tex]n=k\;\;\;k>1[/tex]

[tex]k^3-k=3q[/tex] (Inductive hypothesis)

2. Anta [tex]n=k+1[/tex]

[tex](k+1)^3-(k+1)[/tex]

[tex]k^3+3k^2+3k+1-k-1[/tex]

[tex]k^3-k+3k^2+3k[/tex]

(Vi bruker inductive hypothesis)

[tex]3q+3k^2+3k[/tex]

[tex]= 3(q+k^2+k)[/tex]

[tex]Q.E.D[/tex]

Prøv å bevise d) på samme måte. Poenget er å ha en "inductive hypothesis" som du lager for n=k, for så å bruke det i n=k+1.