Mer induksjon

[Razzy]

[tex]$${Bruk\;induksjon\;til\;{\aa}\;vise\;at \cr 1 + {3^1} + {3^2} + \cdots {3^n} = {{{3^{n + 1}} - 1} \over 2}\;\;for\;n \ge \;0. \cr} $$[/tex]


[tex]$${Utregning: \cr Formulerer\;\det te\;som\;et\;{\aa}pent\;utsagn \cr U\left( n \right):\;\;1 + {3^1} + {3^2} + \cdots {3^n} = {{{3^{n + 1}} - 1} \over 2}\;\;for\;n \ge \;0. \cr} $$[/tex]


[tex]$${Vi\;starter\;med\;{\aa}\;etablere\;induksjonsgrunnlaget.\;\;Vi\;setter\;n = 0\;i\;utsagnet\;og\;f{\aa}r \cr U\left( 0 \right):\;\;{3^0} = {{{3^{0 + 1}} - 1} \over 2} \Leftrightarrow 1 = 1\;som\;er\;et\;sant\;utsagn. \cr} $$[/tex]


[tex]$${Deretter\;sjek\ker \;vi\;induksjonstrinnet.\;Vi\;setter\;n = k\;og\;f{\aa}r: \cr U\left( k \right):\;\;1 + {3^1} + {3^2} + \cdots {3^k} = {{{3^{k + 1}} - 1} \over 2}\;\;for\;k \ge \;0. \cr} $$[/tex]


[tex]$${S{\rm{{\aa}}}\;setter\;vi\;n = k + 1\;og\;f{\rm{{\aa}}}r \cr U\left( {k + 1} \right):\;\;1 + {3^1} + {3^2} + \cdots + {3^{\left( {k + 1} \right)}} = {{{3^{\left( {k + 1} \right) + 1}} - 1} \over 2} = \underline {{{{3^{k + 2}} - 1} \over 2}} \cr} $$[/tex]


[tex]$${N{\aa}\;skal\;vi\;\underline {anta} \;at\;U\left( k \right)\;er\;sant,\;og\;unders{\o}ke\;om\;\det te\;f{\o}rer\;til\;at\;ogs{\aa}\;U\left( {k + 1} \right)\;er\;sant. \cr Vi\;mer\ker \;oss\;at\;venstre\;side\;i\;U\left( {k + 1} \right)\;kan\;skrives \cr 1 + {3^1} + {3^2} + \cdots + {3^k} + {3^{\left( {k + 1} \right)}},\;\;\;der\;{3^{\left( {k + 1} \right)}} \Leftrightarrow {3^k} \cdot {3^1}$$[/tex]


[tex]$${S{\aa}\;\underline {forutsetter} \;U\left( k \right)\;er\;sant.\;Venstre\;side\;av\;U\left( {k + 1} \right)\;kan\;da\;omformes\;slik: \cr \underbrace {1 + {3^1} + {3^2} + \cdots {3^k}}_{ = {{{3^{k + 1}} - 1} \over 2}} + {3^{\left( {k + 1} \right)}} = {{{3^{k + 1}} - 1} \over 2} + {3^{\left( {k + 1} \right)}} = {{{3^{k + 1}} - 1 + 2 \cdot {3^{k + 1}}} \over 2} = \underline {{{{3^{k + 2}} - 1} \over 2}} $$[/tex]


[tex]$$\underline{\underline {Ved\;induksjon\;f{\o}\lg er\;\det \;at\;U\left( n \right)\;er\;sann\;for\;alle\;n \ge 0.}} $$[/tex]


Kilde: ansatte.uit.no/bda006/MatteNotater/LogikkMengder/Induksjonsbevis.pdf

[Vektormannen]

3-tallet til slutt der er ikke ganget med alle de forgående leddene, men bare det siste leddet! Så du kan ikke bytte ut de første leddene med formeluttrykket og gange 3-tallet med dette. Ser du at det blir feil?

Tankegangen din er riktig. Det du har her er følgende (for n = k+1):

[tex]1+3^1 + 3^2 + ... + 3^k + 3^{k+1} = \frac{3^{k+1} - 1}{2} + 3^{k+1}[/tex]

Her er de k+1 første leddene byttet ut med formelen som vi har antatt stemmer for n = k. Da gjenstår det å vise at når vi legger det siste leddet, [tex]3^{k+1}[/tex], til dette, så får vi den ønskede formelen.

[Razzy]

3-tallet til slutt der er ikke ganget med alle de forgående leddene, men bare det siste leddet! Så du kan ikke bytte ut de første leddene med formeluttrykket og gange 3-tallet med dette. Ser du at det blir feil?

Tankegangen din er riktig. Det du har her er følgende (for n = k+1):

[tex]1+3^1 + 3^2 + ... + 3^k + 3^{k+1} = \frac{3^{k+1} - 1}{2} + 3^{k+1}[/tex]

Her er de k+1 første leddene byttet ut med formelen som vi har antatt stemmer for n = k. Da gjenstår det å vise at når vi legger det siste leddet, [tex]3^{k+1}[/tex], til dette, så får vi den ønskede formelen.

Endret - takk mitt orakel!

Her skal man holde tunga rett i munnen:

[tex]$$1 + {3^1} + {3^2} + \cdots + {3^{\left( {k + 1} \right)}} =1 + {3^1} + {3^2} + \cdots + {3^k} + {3^{\left( {k + 1} \right)}}$$[/tex]

Må si at Bjørn Davidsen ved UIT har gode forelesningsnotater

[Vektormannen]

Nå ser det bedre ut ja. Bra! De notatene så oversiktlige og bra ut.

En liten ting; det skal ikke være ekvivalenspiler i det siste du skreiv. Det du mener er jo at de to tingene er det samme, ikke at det ene impliserer det andre og omvendt (det gir jo ikke mening at et matematisk uttrykk impliserer et annet).

[Razzy]

Nå ser det bedre ut ja. Bra! De notatene så oversiktlige og bra ut.

En liten ting; det skal ikke være ekvivalenspiler i det siste du skreiv. Det du mener er jo at de to tingene er det samme, ikke at det ene impliserer det andre og omvendt (det gir jo ikke mening at et matematisk uttrykk impliserer et annet).

Enig, det jeg kunne skrevet var; [tex]$$U\left( n \right) \Rightarrow U\left( {n + 1} \right)\; \Leftrightarrow \;U\left( n \right)\;er\;sann\;for\;alle\;n \ge 0.$$[/tex]

Roet meg litt ned med alle disse pilene og endret svaret ovenfor etter noe jeg fant i boka

[Vektormannen]

Jeg mente i den forrige posten din.

[Razzy]

Jeg mente i den forrige posten din.

Dette kommer jeg til angre på

Men er det ikke riktig at:

[tex]$$1 + {3^1} + {3^2} + \cdots + {3^{\left( {k + 1} \right)}} \Leftrightarrow 1 + {3^1} + {3^2} + \cdots + {3^k} + {3^{\left( {k + 1} \right)}}$$[/tex]

Med ord sier jeg at; [tex]$$1 + {3^1} + {3^2} + \cdots + {3^{\left( {k + 1} \right)}}$$[/tex] er "ekvivalent/likt" eller "identisk likt: [tex]$$ \equiv $$[/tex] med [tex]$$1 + {3^1} + {3^2} + \cdots + {3^k} + {3^{\left( {k + 1} \right)}}$$[/tex] ?

EDIT: Legg merke til at jeg ikke har endret posten enda; er påstålig skjønner du hehe

[Vektormannen]

Når to matematiske uttrykk er like så skriver vi =. Det er betydningen av tegnet =. I dagligtale kan det kanskje gi mening å si at to matematiske uttrykk som er like er ekvivalente, men i matematikk og logikk har det ordet, og symbolet [tex]\Leftrightarrow[/tex], en presis betydning, og det er at den ene logiske påstanden impliserer den andre, og omvendt. Det gir altså mening å si at [tex]x^2 = 9 \ \Leftrightarrow \ x = \pm 3[/tex], men det gir ikke mening å si at [tex]3^2 \ \Leftrightarrow \ 9[/tex] (det korrekte er selvsagt [tex]3^2 = 9[/tex]).

[Razzy]

Når to matematiske uttrykk er like så skriver vi =. Det er betydningen av tegnet =. I dagligtale kan det kanskje gi mening å si at to matematiske uttrykk som er like er ekvivalente, men i matematikk og logikk har det ordet, og symbolet [tex]\Leftrightarrow[/tex], en presis betydning, og det er at den ene logiske påstanden impliserer den andre, og omvendt. Det gir altså mening å si at [tex]x^2 = 9 \ \Leftrightarrow \ x = \pm 3[/tex], men det gir ikke mening å si at [tex]3^2 \ \Leftrightarrow \ 9[/tex] (det korrekte er selvsagt [tex]3^2 = 9[/tex]).

Ok. Har tenkt feil angående bruken av ordet og tegnet, fint å kunne lære å bruke det riktig.

PS: Endret tegnet nå, hehe.