Induksjon

Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk på høyskolenivå. Alle som har kunnskapen er velkommen med et svar. Men, ikke forvent at admin i matematikk.net er spesielt aktive her.

Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Post Reply
Razzy
Grothendieck
Grothendieck
Posts: 819
Joined: 20/09-2010 14:23
Location: Bergen

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 :)
Last edited by Razzy on 04/09-2012 19:55, edited 1 time in total.
Bygg.ing @ Hib - 2 året.
Nebuchadnezzar
Fibonacci
Fibonacci
Posts: 5648
Joined: 24/05-2009 14:16
Location: NTNU

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.
"Å vite hva man ikke vet er og en slags allvitenhet" - Piet Hein
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
Razzy
Grothendieck
Grothendieck
Posts: 819
Joined: 20/09-2010 14:23
Location: Bergen

Nebuchadnezzar wrote: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 :P (er jo en stanhaftig mann selv) ;)

Kjempeflott forklaring Nebu.

EDIT: Endra oppgaven litt, se om du syntes den er grei nå =)
Bygg.ing @ Hib - 2 året.
Nebuchadnezzar
Fibonacci
Fibonacci
Posts: 5648
Joined: 24/05-2009 14:16
Location: NTNU

Jeg ser fortsatt ikke at du argumenterer hvorfor

[tex]2(k-1)! \leq k![/tex]
"Å vite hva man ikke vet er og en slags allvitenhet" - Piet Hein
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
Razzy
Grothendieck
Grothendieck
Posts: 819
Joined: 20/09-2010 14:23
Location: Bergen

Nebuchadnezzar wrote: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?
Bygg.ing @ Hib - 2 året.
Vektormannen
Euler
Euler
Posts: 5889
Joined: 26/09-2007 19:35
Location: Trondheim
Contact:

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?
Elektronikk @ NTNU | nesizer
Razzy
Grothendieck
Grothendieck
Posts: 819
Joined: 20/09-2010 14:23
Location: Bergen

Vektormannen wrote: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] ?
Bygg.ing @ Hib - 2 året.
Vektormannen
Euler
Euler
Posts: 5889
Joined: 26/09-2007 19:35
Location: Trondheim
Contact:

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.
Elektronikk @ NTNU | nesizer
Razzy
Grothendieck
Grothendieck
Posts: 819
Joined: 20/09-2010 14:23
Location: Bergen

Vektormannen wrote: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 :)
Bygg.ing @ Hib - 2 året.
Post Reply