Induktionsbevis olikhet

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å $2^{1-1}\times 1!=1\times 1=1\le 1^1=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 $2^{k-1}\times k!\le k^k$.

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

$2^k\times (k+1)!\le {(k+1)}^{(k+1)}$.

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

$2^k\times (k+1)!=2^{k-1}\times 2\times (k+1)\times k!\le 2(k+1)\times k^k$där det sista steget kommer från antagandet.

Vi sammanfattar och ska då visa att $2(k+1)\times k^k\le {(k+1)}^{k+1}={(k+1)}^k\times (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 $2k^k\le {(k+1)}^k$. Här kan man utveckla HL med binomialsatsen och man får:

$2k^k=k^k+k^k=\le \sum _{t=0}^{k}C(k,t)k^t=\underset{t=0}{\overset{k-1}{(\sum }}C(k,t)k^t)+k^k$.

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:

$k^k\le \sum _{t=0}^{k-1}C(k,t)k^t=C(k,0)+C(k,1)k+C(k,2)k^2+...+C(k,k-1)k^{k-1}$.

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

$C(k,k-1)k^{k-1}=\frac{k!}{(k-1)!1!}{k}^{k-1}=k\times k^{k-1}=k^k$.

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.