Induksjonsbevis, indirekte.

[mikki155]

Jeg lurer på hvordan man kan motbevise en formel ved hjelp av induksjon:

3 + 15 + 63 + ... + 2[sup]2n[/sup]-1 = 6n - 3

Ser om det stemmer for n = 1 :

V. S. :

2[sup][tex]2 \cdot 1[/tex][/sup] - 1 = 3

H. S. :

[tex]6 \cdot 1 - 3 = 3[/tex]

Stemmer for n = 1. Antar at den stemmer for n = k, da må den stemme for n = k +1:

V. S. :

3 + 15 + 63 + ... + 2[sup]2(k+1)[/sup]-1

= 2[sup]2k+2[/sup]-1

= 2[sup]2[/sup] [tex]\cdot[/tex] 2[sup]2k[/sup]-1

= 4 [tex]\cdot[/tex] 2[sup]2k[/sup]-1

H. S. :

[tex]6 \cdot k - 3 + 6 \cdot (k + 1) - 3 = 6k - 3 + 6k + 6 - 3 = 12k[/tex]

Videre:

3 + 15 + 63 + ... + 4 [tex]\cdot[/tex] 2[sup]2k[/sup]-1 = 12k

Hvordan går jeg videre for å formulere at dette er feil? Kan jeg si at formelen er feil siden, høyre siden ikke har en faktor (k + 1)?

Jeg er klar over at man fra begynnelsen av kan motbevise formelen ved å sette inn n = 2, men jeg lurer på hvordan man kan motbevise formelen ved hjelp av induksjon.

[Aleks855]

Siden ingen andre har svart ennå...

Vi sjekker n=1 og finner at det stemmer. (Jeg trenger vel ikke vise dette? )

Vi antar (dog feilaktig, men det vet vi ikke enda ) da at det er sant for n=k.

[tex]3+15+63+\cdots+\(2^{2k}-1\)=6k-3[/tex]

Vi legger til [tex]2^{2(k+1)}-1[/tex] på begge sider og får

[tex]3+15+63+\cdots+\(2^{2k}-1\)+\(2^{2(k+1)}-1\)=6k-3+2^{2(k+1)}-1[/tex]

Som vi bryter opp litt på høyre side:

[tex]3+15+63+\cdots+\(2^{2k}-1\)+\(2^{2(k+1)}-1\)=6k-4+4\cdot 2^{2k}[/tex]



For å fullføre "beviset" må vi påvise at:

[tex]6k-4+4\cdot 2^{2k} = 6(k+1)-3[/tex]

[tex]6k-4+4\cdot 2^{2k} = 6k+3[/tex]

Forenkler dette:

[tex]2^{2k} = \frac{7}{4}[/tex] som ikke er sant for noen naturlige tall k, og påstanden er derfor motbevist.

De som er litt mer kløpre på bevis enn meg må gjerne spytte inn sine 2 cents.

[mikki155]

Åja, jeg ser jeg la til leddet 2[sup]2(k + 1)[/sup] - 1 på venstre side, mens jeg la til [tex]6 \cdot (k + 1) - 3[/tex] på høyre side. Så der tabba jeg meg ut ^^

Takk for fremgangsmåten=) Litt greit å se hvordan det blir når formelen er feil i utgangspunktet.

[Vektormannen]

Jeg tror det blir feil å gjøre det slik Aleks foreslår. Påstanden vi skal bevise her er at formelen ikke stemmer. Som vanlig i et induksjonsbevis, skal vi anta at påstanden stemmer for n = k. Da skal vi altså anta at formelen ikke stemmer for n = k (dette er jo påstanden), for så å vise at da kan den heller ikke stemme for n = k+1.

[mikki155]

Nå ble jeg forvirret xD

Jeg tror jeg ikke forklarte meg godt nok. Det jeg ville frem til var å vise at formelen er feil gjennom et indirekte bevis ved hjelp av induksjon. Men hvis beviset skal være indirekte, må vi jo anta at det oppgitte stemmer, altså at formelen stemmer. Når vi setter n = 1, ser vi jo at den stemmer. Så antar vi at den stemmer for n = k (noe den ikke gjør), og da må den stemme for n = k + 1 (noe den ikke gjør). Og gjennom dette kommer vi til en selvmotsigelse, som gjør at formelen er feil. Det var det jeg mente i utgangspunktet, men det kan hende jeg misforstod deg, Vektormannen.

[Gustav]

Har aldri sett induksjon blitt brukt til å motbevise en formel. Det virker veldig merkelig. Tror nok bevis ved motsigelse er veien å gå.

[Vektormannen]

Om man bare skal motbevise formelen så er et enkelt moteksempel nok, men her forsto jeg det slik at man skal vise at formelen aldri stemmer for noen som helst n? (Det kan selvfølgelig gjøres på enklere måter enn med induksjon)?

[Gustav]

Om man bare skal motbevise formelen så er et enkelt moteksempel nok, men her forsto jeg det slik at man skal vise at formelen aldri stemmer for noen som helst n? (Det kan selvfølgelig gjøres på enklere måter enn med induksjon)?

Vel, den stemmer jo for n=1, så dette kan umulig være riktig.

[fuglagutt]

Det går vel forsåvidt an bare å vise at
[tex]2^{2n}-1 > 6n-3 [/tex] ved høye verdier av n, for deretter å vise at alle verdier av [tex]2^{2n}-1[/tex] er over 0.

Da følger det at summen av de positive verdien MÅ være større enn 6n-3.

[mikki155]

Har aldri sett induksjon blitt brukt til å motbevise en formel. Det virker veldig merkelig. Tror nok bevis ved motsigelse er veien å gå.

Jeg holder med plutarco foreløpig ^^ Særlig siden induksjon ikke er brukt til indirekte bevis.

[Vektormannen]

Om man bare skal motbevise formelen så er et enkelt moteksempel nok, men her forsto jeg det slik at man skal vise at formelen aldri stemmer for noen som helst n? (Det kan selvfølgelig gjøres på enklere måter enn med induksjon)?

Vel, den stemmer jo for n=1, så dette kan umulig være riktig.