1 svar
81 visningar
Manfred123123 6
Postad: 26 sep 16:02

Induktionsbevis olikhet

Man ska visa att 2^(n-1)n! ≤ n^n

Jag har inte skrivit ut hela beviset men i induktionssteget visste jag inte hur man skulle lösa men jag eftersom det var ≤ så tänkte jag att jag kunde titta på = och då fick jag ekvationen längst ner men jag vet ej hur jag ska visa att det stämmer

 

 

Eagle314 176
Postad: 30 sep 21:28

Hej, verkar vara ett (enligt mig) invecklat induktionsbevis. Har inte kollat så länge men har en lösning (som dock bygger på att man känner igen binomialsatsen). Vet inte vilken mängd den ska visas men låt oss säga att det är över alla positiva heltal.

Basfall) Sätt n=1 och man får då 21-1×1!=1×1=111=1. Vilket stämmer och kan ha som basfall.

Antagande) Anta att den gäller för något n=k sådant att det gäller 2k-1×k!kk.

Påstående) Påstå att det om antagandet gäller så gäller det även för n=k+1 och specifikt

2k×(k+1)!(k+1)(k+1).

Vi börjar med att skriva om VL i påståendet och vi får 

2k×(k+1)!=2k-1×2×(k+1)×k!2(k+1)×kkdär det sista steget kommer från antagandet.

Vi sammanfattar och ska då visa att 2(k+1)×kk(k+1)k+1=(k+1)k×(k+1).

Man kan se att både HL och VL ovan innehåller faktorn och då k+1 är positivt (då basfallet var 1) så kan det divideras och man ska då visa att 2kk(k+1)k. Här kan man utveckla HL med binomialsatsen och man får:

2kk=kk+kk=t=0kC(k,t)kt=(t=0k-1C(k,t)kt)+kk.

Här ser man att det finns en k^k term i båda leden och den kan elimineras och man ska då visa en olikhet och genom att utveckla summan så får man:

kkt=0k-1C(k,t)kt=C(k,0)+C(k,1)k+C(k,2)k2+...+C(k,k-1)kk-1.

Kollar man dock endast på sista termen så ser man att den kan förenklas och man får:

C(k,k-1)kk-1=k!(k-1)!1!kk-1=k×kk-1=kk.

Vi ser att den sista termen i HL är lika med VL och det gäller då att resten av termerna C(k,0)+C(k,1)k, osv antingen är positiva eller nollvärda och detta bevisar påståendet och induktionsbeviset är då klart. 

Svara
Close