20 svar
155 visningar
lagminator 29
Postad: 22 jan 20:49

Bevisa olikhet (rekursion)

Jag har kört fast helt på en uppgift här.

Bevisa att (n2)n-1>(n-1)! för alla n=1,2,3...

Jag har tidigare löst den liknande uppgiften Bevisa att 2n>n3 för alla heltal n10, men det känns som att jag kör fast när jag angriper uppgiften på samma sätt.

Så här har jag gjort hittills:

1. Kontrollerar att påståendet är sant för n=1
2. Antar att påståendet stämmer för n=p där p1. Antar då att jag vet att (p2)p-1>(p-1)!

3. Studerar differensen mellan leden för n=p+1

VLp+1- HLp+1 = (p+12)p- p!

I den tidigare uppgiften har jag kunna förenkla och skapa en kedja av olikheter som visat att differensen är större än noll vilket bevisat olikheten för p+1. I denna uppgiften har jag kört fast i det här steget. Hur går jag vidare?

Laguna Online 23276
Postad: 22 jan 21:07

Jag tror det kan ge något att studera kvoten i stället.

lagminator 29
Postad: 22 jan 22:25

Hmm,  det verkar som att jag inte kommer vidare ändå.

feber01 40
Postad: 22 jan 22:41 Redigerad: 22 jan 22:44
lagminator skrev:

Hmm,  det verkar som att jag inte kommer vidare ändå.

Nu har jag bara skummat igenom ditt inlägg men du kan väl skriva VL som en geometrisk summa?

Edit: Det var nog inget förresten. Vet inte hur jag tänkte.

Mogens Online 1711
Postad: 23 jan 02:06

Inget bevis, men en fundering.

Betrakta ett stort n. Helst jämnt, säg 1000

I vänster led har vi då 500999

I höger led har vi 999!

I VL har vi 500*500*500*…*500. Antalet faktorer är 999.

I HL har vi också 999 faktorer: 1*2*3*…*499*500*501*…*999.

HL kan omordnas så att vi skriver:

500*501*499*502*498*…*999*1 =

= 500(500+1)(500–1)(500+2)(500–2)…(500+499)(500–499)

Eftersom (500+k)(500–k) < 500*500 så har vi att produkten i VL är större än den i HL.

 

Så påståendet är säkert riktigt. Nu gäller det bara att göra om detta till ett stringent bevis för andra n än 1000 och se till att det funkar för udda n.

Laguna Online 23276
Postad: 23 jan 08:59

Man verkar behöva använda det man vet om (1 + 1/n)n när n blir stort.

Mogens Online 1711
Postad: 23 jan 12:47
Laguna skrev:

Man verkar behöva använda det man vet om (1 + 1/n)n när n blir stort.

Tror du det, jag var inne på samma spår, men tycker egentligen min bevisidé borde hålla, bara att jag inte iddes genomföra den formellt. 

lagminator 29
Postad: 23 jan 19:52 Redigerad: 23 jan 19:56

Tack för all input! 

Först vill jag säga att jag skrev av uppgiften fel när jag ställde frågan här. Det påverkar inte lösningsmetoden men man skulle visa att olikheten stämde för alla heltal n3. Inte för alla n = 1, 2, 3 ...

 

Jag har klurat mer och landat i det här i alla fall:

VLp+1HLp+1=(p+12)pp!=(p+12)pp(p-1)!=A

 

Eftersom vi antagit att (p2)p-1 > (p-1)! (Induktionsantagandet) så kan vi dra slutsatsen att:

 

A=(p+12)pp(p-1)!>(p+12)pp(p2)p-1=(p+12)p2(p2)p=12·(p+12)p(p2)p=12·(p+1p)p

 

1. Uttrycket (p+1p)paldrig är negativt och växer för positiva p (kan jag anta detta utan att också bevisa det?)

2. För p3 så är 12·(p+1p)p>1 vilket innebär att VLp+1HLp+1>1. Påståendet är alltså sant för alla p3.

 

Skulle ni säga att detta är ett bevis som håller? Eller har jag gjort antaganden som jag egentligen också behöver bevisa först?

Laguna Online 23276
Postad: 23 jan 21:16

Du får nog bevisa det där med ((p+1)/p)p, men det ska inte vara så svårt.

Mogens Online 1711
Postad: 23 jan 22:33 Redigerad: 23 jan 22:39

(p+1)/p är större än 1 så [(p+1)/p]p är förstås också större än 1.

Vi vet iofs att [(p+1)/p]p går mot e när p går mot oändligheten, men det betyder inte att det är växande hela tiden. 

En litet drastisk lösning är att derivera: d [(p+1)/p]p /dp = p[(p+1)/p]p–1 [1–1/p2] som är större än noll, alltså är [(p+1)/p]p växande. (För p ≥ 3.)

Jag tycker beviset verkar hålla. Men jag tror att det kan formuleras koncisare; det är ganska svårtolkat.

 

Mitt bevis utnyttjar inte induktion:

1. Låt n vara jämnt = 2k. 

Då är påståendet att (k)2k–1 > (2k–1)!      (för k ≥ 2)

VL = k*k*…k          (2k–1 faktorer)

HL = 1*2*3*…*k*…(k+k–1) =

= k*(k+1)(k–1)*(k+2)(k–2)*…*(k+k–1)(k–k+1)    (Också 2k–1 faktorer)

Vi ser att varje par av parenteser (k+j)(k–j) i högra ledet är mindre än

motsvarande par k*k i vänstra ledet.

Så påståendet är sant för jämna n.

 

2. Låt n vara udda = 2k+1       (k ≥ 1)

Då är påståendet att [(2k+1)/2]2k > (2k)!

VL = (k+1/2)2k+1  = (k+1/2)(k+1/2)*… *(k+1/2)(k+1/2)           (2k faktorer)

HL = 1*2*3*…(k–1)(k+1)…(k+k) = (också 2k faktorer)

= (k+1)(k–1)*(k+2)(k–2)*…*(k+k)*1

Åter kommer varje par av faktorer (k+1/2)(k+1/2) vara större än (k+j)(k–j) 

eftersom j > 1/2

Så påståendet sant för både jämna och udda n > 2.

 

Detta bevis ser krångligare ut än det är.

Laguna Online 23276
Postad: 23 jan 23:55
Mogens skrev:

(p+1)/p är större än 1 så [(p+1)/p]p är förstås också större än 1.

Vi vet iofs att [(p+1)/p]p går mot e när p går mot oändligheten, men det betyder inte att det är växande hela tiden. 

En litet drastisk lösning är att derivera: d [(p+1)/p]p /dp = p[(p+1)/p]p–1 [1–1/p2] som är större än noll, alltså är [(p+1)/p]p växande. (För p ≥ 3.)

Jag är inte med på din derivering där.

Mogens Online 1711
Postad: 24 jan 12:03
Laguna skrev:

Jag är inte med på din derivering där.

EDIT: 

d [(p+1)/p]p /dp = p[(p+1)/p]p-1  [1–1/p2]

 

Helt åt skogen, inte många siffror rätt där.

Tack Laguna!

Laguna Online 23276
Postad: 24 jan 12:23 Redigerad: 24 jan 12:24

Står det inte samma som förut? Jag får nån logaritm där också.

Prova att skriva uttrycket som ep*ln(1+1/p).

 

Mogens Online 1711
Postad: 24 jan 22:42
Laguna skrev:

Står det inte samma som förut? Jag får nån logaritm där också.

Prova att skriva uttrycket som ep*ln(1+1/p).

 

Jo, det står samma som förut. Kanske otydligt, jag ville säga att det var åt skogen :)

Jo jag deriverade rätt sedan, men det blev jobbigt att dra slutsatser av riktiga derivatan. Derivering kändes inte som grejen här. Men vill någon annan försöka så ok. Blev avbruten så jag lämnade det.

Laguna Online 23276
Postad: 24 jan 22:48

Jag drog inte heller några slutsatser av derivatan. Ditt bevis var mycket bättre.

lagminator 29
Postad: 25 jan 08:34 Redigerad: 25 jan 08:35
Mogens skrev:

 

2. Låt n vara udda = 2k+1       (k ≥ 1)

Då är påståendet att [(2k+1)/2]2k > (2k)!

VL = (k+1/2)2k+1  = (k+1/2)(k+1/2)*… *(k+1/2)(k+1/2)           (2k faktorer)

HL = 1*2*3*…(k–1)(k+1)…(k+k) = (också 2k faktorer)

= (k+1)(k–1)*(k+2)(k–2)*…*(k+k)*1

Åter kommer varje par av faktorer (k+1/2)(k+1/2) vara större än (k+j)(k–j) 

eftersom j > 1/2

Så påståendet sant för både jämna och udda n > 2.

När antalet faktorer är jämt kan man väl inte para ihop konjugaten på det sätt du gjort?

Anta att 2k=6 och vi har faktorerna 1*2*3*4*5*6. Parar jag som exemplet ovan börjar från vänster blir det. (4*2)(5*1)(6*3) dvs: (k+1)(k-1)(k+2)(k-2)(k+k)(k). Måste man inte visa att (k+k)(k) som har brutit mönstret av konjugat inte "väger över" och (2k)! plötsligt blir större trots att alla tidigare par varit mindre än varje motsvarande par (k+1/2)(k+1/2). Men det kanske är en enkel sak att visa iofs.

Att jag så envist försöker göra en induktionsbevis har att göra med att uppgiften kommer från ett kapitel om induktion, så jag bara antog att det var så jag "borde" lösa uppgiften.

Tack båda för att ni tar er tid!

Mogens Online 1711
Postad: 25 jan 13:47

lagminator, 

 

Jag tror också att det finns någon smart induktionslösning, och det vore tillfredsställande att hitta den. Jag är litet hämmad av att jag oftast saknar möjlighet att använda papper och penna när jag skriver lösningar utan får göra beräkningarna i huvudet. Men om vi kollar detta med jämnt och udda:

Udda:

n = 7 ger påståendet:

(7/2)6 > 6!        <=>

3,5*3,5*3,5*3,5*3,5*3,5 > 1*2*3*4*5*6

HL kan skrivas [(3,5+0,5)(3,5–0,5)]*[(3,5+1,5)(3,5–1,5)]*[(3,5+2,5)(3,5–2,5)] 

som enligt konjugatregeln är mindre än VL. Resonemanget kan utföras för godtyckligt udda n ≥ 3.

Jämnt: 

n = 8 ger påst:

47 > 7!   <=>

4*4*4*4*4*4*4 > 1*2*3*4*5*6*7

HL kan skrivas

4*[(4+1)(4–1)]*[(4+2)((4–2)]*[(4+3)(4–3)]

som är mindre än VL.

Så jag tror min bevisidé håller (fast jag kan ha skrivit fel någonstans när jag skrev ut det. Vi lämnar åt forskningen att kolla detaljerna.)

Om jag hittar en lucka ska jag ta itu med induktionen :)

Mogens Online 1711
Postad: 25 jan 15:40

Nu har jag tittat en stund, men utan resultat.

Jag gick vidare från lagminators resultat att om f(n) = [(n+1)/n)]n är en växande följd så är vi klara, men det var inte så lätt.

Man kan inse att t ex f(1000) – f(999) < 0,0000014 så den växer inte så fort…

Jag landade i att om [(n+1)/n]n * [(n–1)/n]n–1 > 1 så är beviset klart. För n = 1000 blir vänsterledet ≈ 1,0000005, marginalen är smal.

Laguna Online 23276
Postad: 25 jan 15:52

Ett sätt är att visa att ln(1+1/n) > 1/(n+1).

Hm, det kanske går om man deriverar en gång till...

Mogens Online 1711
Postad: 26 jan 01:29
Laguna skrev:

Ett sätt är att visa att ln(1+1/n) > 1/(n+1).

Hm, det kanske går om man deriverar en gång till...

Ja, jag tror att jag fick till det.

Vi ska visa att ln(1+1/n) – 1/(n+1) > 0 när n är ”stort” (typ ≥ 3)

Sätt t = 1/n och låt t gå mot 0+.

Vi får ln(1+t) – t/(1+t) = (maclaurin och geom serie) =

(t – t2/2 + t3/3 - …) – (t – t2 + t3 - …) = t2/2 – 2t3/3 + …

som är > 0 för t ≤ 1/3. q.e.d.

lagminator 29
Postad: 26 jan 07:52

Mogens skrev:

Visa spoiler

lagminator, 

 

Jag tror också att det finns någon smart induktionslösning, och det vore tillfredsställande att hitta den. Jag är litet hämmad av att jag oftast saknar möjlighet att använda papper och penna när jag skriver lösningar utan får göra beräkningarna i huvudet. Men om vi kollar detta med jämnt och udda:

Udda:

n = 7 ger påståendet:

(7/2)6 > 6!        <=>

3,5*3,5*3,5*3,5*3,5*3,5 > 1*2*3*4*5*6

HL kan skrivas [(3,5+0,5)(3,5–0,5)]*[(3,5+1,5)(3,5–1,5)]*[(3,5+2,5)(3,5–2,5)] 

som enligt konjugatregeln är mindre än VL. Resonemanget kan utföras för godtyckligt udda n ≥ 3.

Jämnt: 

n = 8 ger påst:

47 > 7!   <=>

4*4*4*4*4*4*4 > 1*2*3*4*5*6*7

HL kan skrivas

4*[(4+1)(4–1)]*[(4+2)((4–2)]*[(4+3)(4–3)]

som är mindre än VL.

Så jag tror min bevisidé håller (fast jag kan ha skrivit fel någonstans när jag skrev ut det. Vi lämnar åt forskningen att kolla detaljerna.)

Om jag hittar en lucka ska jag ta itu med induktionen :)

 

 

Nu ser jag det också. Inga invändningar! Betydligt smidigare än induktionsgrejen. (I alla fall så som jag försökt lösa det)

Mogens skrev:


Ja, jag tror att jag fick till det.

Vi ska visa att ln(1+1/n) – 1/(n+1) > 0 när n är ”stort” (typ ≥ 3)

Sätt t = 1/n och låt t gå mot 0+.

Vi får ln(1+t) – t/(1+t) = (maclaurin och geom serie) =

(t – t2/2 + t3/3 - …) – (t – t2 + t3 - …) = t2/2 – 2t3/3 + …

som är > 0 för t ≤ 1/3. q.e.d.

 

Bra jobbat! Saker jag inte kan,(än hoppas jag!), men jag litar på att det stämmer!

Svara Avbryt
Close