Induksjon

[Janhaa]

Hvordan går man fram på induksjonsoppgava under:

Bevis ved induksjon at:

[tex]n! < (n/2)^n[/tex]

for
[tex]n\geq 6[/tex]
***
har prøvd meg på følgende:

[tex]n=6[/tex]
[tex]LHS=720[/tex]
og
[tex]RHS=729[/tex]
OK
og setter så
[tex]n=k+1[/tex]
slik at:
[tex](k+1)!<\left(\frac{k+1}{2}\right)^{k+1}[/tex]

[tex](k+1)!<\left(\frac{k+1}{2}\right)^{k}\left(\frac{k+1}{2}\right)[/tex]

[tex](k+1)k!<\left(\frac{k+1}{2}\right)^{k}\left(\frac{k+1}{2}\right)[/tex]

[tex](k+1)\left(\frac{k}{2}\right)^k<\left(\frac{k+1}{2}\right)^{k}\left(\frac{k+1}{2}\right)[/tex]
der er jo åpenbart

[tex]\left(\frac{k+1}{2}\right)^k > \left(\frac{k}{2}\right)^{k}[/tex]
men
[tex](k+1)>\left(\frac{k+1}{2}\right)[/tex]

derimot vokser jo:

[tex]\left(\frac{k+1}{2}\right)^k > \left(\frac{k}{2}\right)^{k}[/tex]

raskest...

holder dette?

[Nebuchadnezzar]

Føler alltid det er mer logisk å gå fra $k$ til $k+1$ på ulikheter. Selv om begge veier er like riktige.

Anta at $k! < (k/2)^k$. Ganger med $(k+1)$ på begge sider og merker meg at $(k+1)\cdot k! = (k+1)!$ så

$ \hspace{1cm}
\begin{align*}
(k+1)! & < (k+1) (k/2)^k \\
& < \left( \frac{k+1}{2} \right) 2 \left( \frac{k}{2} \right)^{k} \\
& < \left( \frac{k + 1}{2} \right) \left( \frac{k+1}{2} \right)^{k}
= \left( \frac{k + 1}{2} \right)^{k+1}
\end{align*}
$

Å vise siste overgang trenger noe kløkt. $2 (k/2)^k < ((k+1)/2)^k$. Ved å dele på $(k/2)^k$ på begge sider fås

$ \hspace{1cm}
2 < \left( 1 + \frac{1}{k} \right)^k
$

Som åpenbart holder for $k>1$ siden $(1+1)^1 = 2$ og funksjonen er voksende (går mot $e$). Dette fullfører induksjonsbeviset.

[DennisChristensen]

Først må vi vise at $n^n \leq \frac{(n+1)^n}{2}$ for alle $n \in \mathbb{N}$.
Ideen er å vise at følgen $a_n = \left(\frac{n+1}{n}\right)^n = \left(1 + \frac{1}{n}\right)^n$ er voksende for alle $n$:

Lemma 1: For alle $n \in \mathbb{N}$ har vi at $\frac{n^2 + n + 1}{(n+1)^2} \geq \frac{n+1}{n+2}$.

Bevis: Vi har at $(n+2)(n^2 + n + 1) = (n+2)\left( (n+1)^2 - n \right) \geq (n+1)^3$.
$\therefore \frac{n^2 + n + 1}{(n+1)^2} \geq \frac{n+1}{n+2},$ hvilket skulle vises.


Lemma 2: for alle $n \in \mathbb{N}, n^n \leq \frac{(n+1)^n}{2}$.

Bevis:

$\begin{align*} \frac{a_{n+1}}{a_n} & = \frac{\left(1 + \frac{1}{n+1}\right)^{n+1}}{\left(1 + \frac{1}{n}\right)^n} \\
& = \left(\frac{n(n+2)}{(n+1)^2}\right)^n\left(1 + \frac{1}{n+1}\right) \\
& = \left(1 - \frac{1}{(n+1)^2}\right)^n\left(1 + \frac{1}{n+1}\right) \\
& \geq \left(1 - \frac{n}{(n+1)^2}\right)\left(1 + \frac{1}{n+1}\right) \text{ fra Bernoullis ulikhet} \\
& = \left(\frac{n^2 + n + 1}{(n+1)^2}\right)\left(1 + \frac{1}{n+1}\right) \\
& \geq \left(\frac{n+1}{n+2}\right)\left(1 + \frac{1}{n+1}\right) \text{ fra lemma 1} \\
& \left(\frac{1}{1 + \frac{1}{n+1}}\right)\left(1 + \frac{1}{n+1}\right) \\
& = 1, \end{align*}$

så $a_{n+1} \geq a_n,$ hvilket betyr at $(a_n)$ er voksende.

Ettersom $a_1 = 2$ ser vi at for alle $n \in \mathbb{N}, n^n \leq \frac{(n+1)^n}{2},$ hvilket skulle vises.

Vi kan nå gå løs på induksjonsbeviset:

Induksjon: Anta at det finnes en $n \in \mathbb{N}_{\geq 6}$ slik at $n! < \left(\frac{n}{2}\right)^n$.

Da har vi at
$\begin{align*} (n+1)! & = (n+1)n! \\
& < (n+1) \left(\frac{n}{2}\right)^n \\
& = \frac{n+1}{2^n}n^n \\
& \leq \frac{n+1}{2^n} \frac{(n+1)^n}{2} \text{ fra lemma 2} \\
& = \left(\frac{n+1}{2}\right)^{n+1}, \text{ hvilket fullfører induksjonen.}\end{align*}.$

[Nebuchadnezzar]

Vits å koke 10 høner på en fjær? :p Det er elementert å vise at $\log(1+x)/x$ er synkende for alle $x>0$. For eksempel drøft den deriverte eller se at logaritmen er konkav for alle verdier. Siden $1/n$ er synkende betyr dette at $\log( 1 + 1/n) / (1/n)$ økende. Siden $e$ er positiv kan vi opphøye uttrykket i dette og fortsatt ha en økende funksjon. Med andre ord så er $\exp\bigl( n \log ( 1 + 1/n) \bigr) = (1 + 1/n)^n $ voksende. Som var det vi ønsket å vise. Alternativt kan en og studere binomial-formelen.

Eller bruke AM-GM ulikheten. For alle $n$ så har vi $ \sqrt[n+1]{x_{1}x_{2}\cdots x_{n+1}}<\frac{x_{1}+x_{2}+\ldots+x_{n+1}}{n+1} $. Ved å sette $x_1=1$ og $x_2 = x_3 = \cdots = x_{n+1} = 1 + \frac{1}{n}$ gir ulikheten oss

$ \hspace{1cm}
\left( 1 + \frac{1}{n}\right)^{n/(1+n)} < \frac{1 + n \left( 1 + \frac{1}{n} \right) }{ 1 + n } = 1 + \frac{1}{1+n}
$

Ved å opphøye begge sider i $1+n$ har en vist at $a_n < a_{n+1}$ som ønsket. Menne mye styr for lite ^^ Uansett fin løsning dennis!

[Janhaa]

takker begge to!