Induksjon

[Razzy]

Oppgaven:

Vis at [tex]$$\;{2^n} \le \left( {n - 1} \right)!\;$$[/tex] for alle [tex]$$n \ge 6$$[/tex].


Løsningsforslag:

Formulerer oppgaven som et åpent utsagn:

[tex]$$U\left( n \right):\;\;\;{2^n} \le \left( {n - 1} \right)!\;\;\;for\;alle\;n \ge 6.$$[/tex]


Induksjonsgrunnlaget: Setter [tex]n=6[/tex] og utsagnet blir:

[tex]$$U\left( 6 \right):\;\;\;{2^6} \le \left( {6 - 1} \right)!\;\;\;for\;alle\;n \ge 6.$$[/tex]

[tex]U\left( 6 \right):\;\;\;64 \le 120 \;som\; er\; et\; sant\; utsagn.[/tex]


Induksjonstrinnet: Vi setter [tex]n=k[/tex] og får;

[tex]$$U\left( k \right):\;\;\;{2^k} \le \left( {k - 1} \right)!\;\;\;for\;alle\;k \ge 6.$$[/tex]


Så setter vi [tex]n=k+1[/tex] og får;

[tex]$$U\left( k+1 \right):\;\;\;{2^{k+1}} \le \left( {(k+1) - 1} \right)!=k!\;\;\;for\;alle\;k \ge 6.$$[/tex]


Vi omformer venstre side av [tex]$$U\left( {k + 1} \right)$$[/tex] og forutsetter at [tex]$$U\left( k \right)$$[/tex] er sant:

[tex]$${2^{k + 1}} = {2^k} \cdot 2 \le \left( {k - 1} \right)!\; \cdot \;2 \le k!$$[/tex]

Der vi ser at: [tex]$$2\left( {k - 1} \right)! \le k!=2 \cdot k! \le k \cdot k!$$[/tex]

Som stemmer da [tex]$$k \ge 6 \; for \; alle\; k.$$[/tex]


[tex]$$ \Rightarrow $$[/tex] Da [tex]$${2^{k + 1}} \le 2 \cdot k! \le k \cdot k!$$[/tex] er induksjonsgrunnlaget er sant, og induksjonstrinnet også er sant, har vi bevist påstanden.



EDIT: Går det an å gjøre slik også? Selvfølgelig din verson var enkel og lett å forstå, men prøver å følge et oppsett her

[Nebuchadnezzar]

Jeg klarer ikke å se det lett, dessverre

Et alternativt er å anta at likheten

[tex]2^k \, \leq \, (k-1)! [/tex]

Stemmer, ganger vi likheten med [tex]k[/tex] får vi

[tex]k \cdot 2^k \, \leq \, k! [/tex]

(fyll inn detaljene selv ) og [tex]2^{k+1} \, \leq \, k \cdot 2^k[/tex] siden [tex]k \, > \, 6 [/tex]

Altså kan vi skrive

[tex]2^{k+1} \, \leq \, k \cdot 2^k \, \leq \, k![/tex]

som var det vi ønsket å vise. Husk å alltid begrunn påstandene dine, og ikke bare ut i fra grafer. Disse kan ofte unnlate å fortelle hele sannheten.

[Razzy]

Jeg klarer ikke å se det lett, dessverre

Et alternativt er å anta at likheten

[tex]2^k \, \leq \, (k-1)! [/tex]

Stemmer, ganger vi likheten med [tex]k[/tex] får vi

[tex]k \cdot 2^k \, \leq \, k! [/tex]

(fyll inn detaljene selv ) og [tex]2^{k+1} \, \leq \, k \cdot 2^k[/tex] siden [tex]k \, > \, 6 [/tex]

Altså kan vi skrive

[tex]2^{k+1} \, \leq \, k \cdot 2^k \, \leq \, k![/tex]

som var det vi ønsket å vise. Husk å alltid begrunn påstandene dine, og ikke bare ut i fra grafer. Disse kan ofte unnlate å fortelle hele sannheten.

Ta dette som et kjempe komplemang: Men av og til er det talentet ditt irriterende! hehe (er jo en stanhaftig mann selv)

Kjempeflott forklaring Nebu.

EDIT: Endra oppgaven litt, se om du syntes den er grei nå =)

[Nebuchadnezzar]

Jeg ser fortsatt ikke at du argumenterer hvorfor

[tex]2(k-1)! \leq k![/tex]

[Razzy]

Jeg ser fortsatt ikke at du argumenterer hvorfor

[tex]2(k-1)! \leq k![/tex]

Skriver jo: [tex]$$2\left( {k - 1} \right)! \le k! = 2\cdot k! \le k\cdot k!$$[/tex]

der [tex]$$2\cdot k! \le k\cdot k!$$[/tex] stemmer for [tex]$$k \ge 6$$[/tex].


Når [tex]$$2\cdot k! \le k\cdot k!$$[/tex] er nødt til å stemme fordi k aldri er mindre enn 6, og [tex]$$2\cdot k! \le k\cdot k!$$[/tex] er det samme som: [tex]$$2\left( {k - 1} \right)! \le k!$$[/tex].

Må også dette være gyldig.


Hvorfor argumenterer du bedre enn meg med ditt forslag?

[Vektormannen]

Det er egentlig en smakssak tror jeg. Det er like riktig å argumentere slik du gjør. Begge deler ender opp med å begrunnes av at k > 6 > 2.

Det kom ikke så tydelig frem syns jeg, men jeg ser jo nå at du mente det. Det jeg stusser på er linjen [tex]2(k-1)! \leq k! = 2 k! \leq k \cdot k![/tex]. Der står det at [tex]k! = 2k![/tex]. Er det riktig?

[Razzy]

Det er egentlig en smakssak tror jeg. Det er like riktig å argumentere slik du gjør. Begge deler ender opp med å begrunnes av at k > 6 > 2.

Det kom ikke så tydelig frem syns jeg, men jeg ser jo nå at du mente det. Det jeg stusser på er linjen [tex]2(k-1)! \leq k! = 2 k! \leq k \cdot k![/tex]. Der står det at [tex]k! = 2k![/tex]. Er det riktig?

Dette: [tex]k! = 2k![/tex] må være feil. Fikk du dette fra: [tex]2 k! \leq k \cdot k![/tex] ?

[Vektormannen]

Nei, det er som sagt linjen [tex]2(k-1)! \leq k! = 2k! \leq k \cdot k![/tex] jeg har problemer med. Kan du forklare hva du mener her? Her står det jo bl.a. k! = 2k!, gjør det ikke?

Jeg tror egentlig du kan droppe den linjen. Hvis du forandrer litt på linjen rett ovenfor slik:

[tex]2^{k+1} = 2^k \cdot 2 \leq (k-1)! \cdot 2 \leq (k-1)! \cdot k = k![/tex]

Og begrunner det med at [tex]k \geq 6 > 2[/tex] slik du gjør nedenfor, så er det egentlig ok.

[Razzy]

Nei, det er som sagt linjen [tex]2(k-1)! \leq k! = 2k! \leq k \cdot k![/tex] jeg har problemer med. Kan du forklare hva du mener her? Her står det jo bl.a. k! = 2k!, gjør det ikke?

Jeg tror egentlig du kan droppe den linjen. Hvis du forandrer litt på linjen rett ovenfor slik:

[tex]2^{k+1} = 2^k \cdot 2 \leq (k-1)! \cdot 2 \leq (k-1)! \cdot k = k![/tex]

Og begrunner det med at [tex]k \geq 6 > 2[/tex] slik du gjør nedenfor, så er det egentlig ok.

[tex]2(k-1)! \leq k! = 2k! \leq k \cdot k![/tex]

Det som skulle skjedd ovenfor var at jeg hadde en ulikhet:

[tex]2(k-1)! \leq k![/tex]

Så ganget jeg begge sider med k! og fikk:

[tex]2k! \leq k \cdot k![/tex]

osv...

Jeg skrev aldri at: [tex]k! = 2k![/tex] men at denne ulikheten: [tex]2(k-1)! \leq k![/tex] = denne ulikheten: [tex]2k! \leq k \cdot k![/tex]



Uansett, har fått det slik jeg forstår det nå:

Så setter vi [tex]n=k+1[/tex] og får;

[tex]$$U\left( k+1 \right):\;\;\;{2^{k+1}} \le \left( {(k+1) - 1} \right)!=k!=\left( {k - 1} \right) \cdot k! \;\;\;for\;alle\;k \ge 6.$$[/tex]


Vi omformer venstre side av [tex]$$U\left( {k + 1} \right)$$[/tex] og forutsetter at [tex]$$U\left( k \right)$$[/tex] er sant:

[tex]$${2^{k + 1}} = {2^k} \cdot 2 \le \left( {k - 1} \right)! \cdot 2 \le k!=\left( {k - 1} \right) \cdot k!$$[/tex]

og så er det skrive når k er større enn lik 6 osv... som du sa