Latin
Induktionsbevis - rigtig fremgangsmåde?
Hej,
Jeg sidder og læser til eksamen i diskret matematik og har lidt svært ved induktionsbeviser samt at finde ud af hvorvidt min fremgangsmåde er rigtig og forkert (specielt ved bevis af uligheder). Jeg vil egentlig bare vide om min fremgangsmåde korrekt for nedenstående opgave (i forhold til hvordan et induktionsbevis i uligheder skal se ud), da jeg ikke har noget facit i min bog, desværre.
_______________________
Bevis ved induktion for alle heltal n ≥ 4 at det gælder at
P(n) ≡ n! > n2
Det første jeg gør er at bevise for basistilfældet, dvs.:
P(4) ≡ 4! = 4 * 3 * 2 = 24 > 42 = 16 hvilket er sandt.
Derefter antager vi at p(k) gælder, altså:
P(k) ≡ k! > k2 for alle heltal k ≥ 4 (dette er vores induktionshypotese)
Vi skal herefter bevise P(k+1):
P(k+1) ≡ (k+1)! > (k+1)2 = k2+1+2k
Ved brug af induktionshypotesen:
(k+1)! = (k+1)k! > (k+1)*k2 = k2+ k3
Herefter har vi at siden k ≥ 4 må det gælde at k3 > 2k + 1, derfor får vi:
(k+1)! > k2 + k3 > k2 + 2k + 1 = (k+1)2
Hvilket er det vi skulle bevise.
___________________________
Håber på at nogle med forstand på diskret matematik kan svare mig på, om det er korrekt - specielt med hensyn til, når jeg bruger det at k3 > 2k + 1. Og undskyld at jeg har komme til at trykke forkert så mit spørgsmål ligger under latin >_>
Svar #1
02. januar 2015 af Andersen11 (Slettet)
Du har ikke vist, at k3 > 2k + 1 for k ≥ 4.
Man antager, at P(k) er sandt, dvs. at k! > k2 .
Vi har så
(k+1)! = (k+1)·k! > (k+1)·k2
Ligningen k2 = k+1 har rødderne k = (1 ± √5)/2 , så for k > (1 + √5)/2 gælder der k2 > k+1 .
Da 4 > (1 + √5)/2 , har vi derfor for k ≥ 4, at
(k+1)! = (k+1)·k! > (k+1)·k2 > (k+1)·(k+1) = (k+1)2
hvilket beviser P(k+1).
Denne tråd burde være under matematik, ikke latin.
Svar #2
02. januar 2015 af Lynd (Slettet)
Og ja, er godt klar over det men den lod mig ikke ændre forum.
Svar #3
02. januar 2015 af Andersen11 (Slettet)
#2
Jeg benyttede, at for et 2.-gradspolynomium f(x) = ax2 + bx + c , hvor a > 0 , er polynomiet positivt uden for rødderne og negativt mellem rødderne.
Hvis man skal løse uligheden k3 > 2k + 1 , skal man først bestemme monotoniforholdene for polynomiet
g(x) = x3 - 2x -1 .
Her finder man g '(x) = 0 ⇒ x = ±√(2/3) , og dermed, at g(x) er voksende for x > √(2/3) . Dernæst skal man løse ligningen g(x) = 0 , og man ser let, at g(-1) = 0 , så g(x) = (x+1)(x2 -x -1) , og dermed
g(x) = 0 ⇔ x = -1 ∨ x = (1 ± √5)/2 .
Heraf ser man så, at for x > (1 + √5)/2 er g(x) > 0 , dvs. for k ≥ 4 gælder der k3 > 2k + 1 .
Svar #4
02. januar 2015 af Lynd (Slettet)
Svar #5
02. januar 2015 af Andersen11 (Slettet)
#4
Det drejer sig her om at bevise, at en ulighed er opfyldt for at få induktionen til at køre. Det kan man i dette tilfælde gøre ved at benytte resultatet af en monotoniundersøgelse.
Skriv et svar til: Induktionsbevis - rigtig fremgangsmåde?
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.