Induktion: n^2 =< n!

Jeg har selv lavet lidt af det:

Basis (må være): n=4

4^2 =< 4!

16 =< 24    hvilket selvfølgelig er sandt

Hvis jeg så uden, at vide det antager at det også er sandt for en givent k:

k^2 =< k!

Så skal jeg jo bevise at det også er sandt for k+1:

(k+1)^2 =< (k+1)!

Det største problem er fakultet. Jeg aner intet om de regneregler der gælder for fakultet. Er der nogen måde hvorpå jeg kan reducere det?

Du er startet rigtigt godt Reglen for fakultet er følgende

(k+1)!=(k+1)(k!)

Benyt denne i det du allerede har skrevet

Tak for svaret.

Hvis jeg så skulle gøre noget ved højre side af det du skrev, hvad kunne jeg så gøre?

Må man fx gange (k!) ind i den anden parantes? Hvilket jo ville blive k * k! + k!

Jeg må sige, at jeg er lidt lost. Problemet er, at jeg ikke ved hvad jeg skal ende med. Alle de induktionseksempler jeg har set er så forskellige, så man har ikke noget man kan sammenligne med.

Jeg ved dog, at jeg skal bruge min induktionsantagelse og lægge de to sammen (hvis man kan gå til skridtet i mit basis skridt, og man ligemeget hvilket skridt man står på, altid kan gå et skridt frem)..

Eller nej det med, at gange ind i parantesen kan man ikke. Det giver ihvertfald ikke det samme resultat hvis jeg fx tildeler k en værdi.

Hvordan skal jeg generelt forholde mig til k! ? Hvilke andre regneregler gælder? 'Opfører' det sig som fx ubekendte eller lign?

udregner man det du fik i #1 med hintet fra #2;   k² + 2k + 1 ≤ k!*k + k!  sammenlign 2k + 1 med k!*k og k²  med  k!  Hvad kan du så sige om uligheden?

Jeg må indrømme, at jeg stadig ikke ved hvor jeg skal hen.

Jeg kan godt se, at du sammenligner 2 led på den ene side med et led på den anden side og et led på den ene side med et led på den anden side. Jeg kan også godt se hvordan k^2 og k! er stigende - hvis man fx tegner en graf, men er det bevis nok?

Du kan alternativt gøre sådan

(k+1)^2 <= (k+1)!  <=>
(k+1)^2 <= (k+1)(k!)  <=>
k+1 <= k!

Men af antagelsen har du k^2 <= k!, og da k+1 <= k^2 (for k>=4) gælder

k+1 <= k^2 <= k!.

Dermed er du færdig.

Okay nu er jeg godt med. Dog forstår jeg ikke hvordan du kan sige "og da k+1 <= k^2 for k>=4"

Jeg kan godt se dette:

k+1 <= k!

k^2 <= k!

Hvis det havde været = og ikke <= så kunne man jo sige: k+1 = k^2, men da der også er <, kan man da ikke sige noget om forholdet mellem k+1 og k^2

Eller er det her man bruger sit basisskridt og kigger på k = 4 ?

Jeg prøver at vise (k+1)<=k!. For at gøre dette laver jeg en vurdering der er, at (k+1) er i hvert fald mindre end k^2, dette gælder dog ikke for alle k (fx. ikke k=1), men det er ikke noget problem, da vi kun betragter k>=4 for hvilket det gælder.

Da du desuden har antaget, at k^2<=k! kan du nu vise (k+1)<=k! idet du kan skyde k^2 ind i mellem som jeg gør i #7.

Jeg tror jeg er helt med nu. Problemet er dog, at jeg ikke forstår hvordan jeg kan sige om jeg er færdig eller ej, med følgende:

k+1 <= k^2 <= k!

Det giver selvfølgelig mening, så længe k<=4, men er det virkelig et bevis? Jeg skal jo vise, for hvilke positive heltal det gælder.

Grunden til du måske ikke forstår det er, at det gælder for større end eller lig 4, ikke mindre!

Hvis du stadig ikke forstår det så spørg endelig igen.

Når ja, det var bare en skrivefejl. Jeg ved godt, at "k+1 <= k^2 <= k!" kun gælder for k >= 4.

Men er det virkelig SVARET (som i resultatet) på et (læs: dette) induktionsbevis?

Ja, det er svaret. Når du har vist

k+1 <= k^2 <= k!

har du pga. ensbetydende pilene, at

(k+1)^2 <= (k+1)!

Dette er vist ved antagelse af k^2<=k!. Da du desuden har vist 4^2<=4! har du lavet dit induktionsbevis.

Rent logisk har du vist det passer for k=4, desuden har du vist, at når det passer for k=4 gælder det for k=4+1=5, dermed har du vist, at når det passer for k=5 passer det for k=5+1=6, osv. Dermed gælder det for alle k større end eller lig 4.

Ja okay. Så får man den "trappe" effekt, hvor man kan gå til skridt 4 og man altid kan gå 1 skridt op.

Rigtig mange gange tak for hjælpen. Det har været en stor hjælp. Jeg tror rent faktisk jeg har fået helt godt styr på induktionsbeviser - som har været vildt svært indtil nu.

Tak.