Vollständige Induktion einer Ungleichung

21.10.2015, 18:04

Felixkeeg

Vollständige Induktion einer Ungleichung

Meine Frage:
Hi, eine Frage zur vollständigen Induktion
Für alle k Element der natürlichen Zahlen gilt:

$\begin{eqnarray*} k!\geq 2^{k-1} \end{eqnarray*}$

Meine Ideen:
Induktionsstart: k=1
$\begin{eqnarray*} 1!\geq 2^{1-1} = 1\geq 1 \end{eqnarray*}$ Stimmt so. Toll.
Induktionsschritt: k->k+1
$\begin{eqnarray*} (k+1)!\geq 2^{(k+1)-1} \end{eqnarray*}$ Kann man umformen zu:
$\begin{eqnarray*} k!*(k+1)\geq 2^{(k-1)+1} \end{eqnarray*}$ und weiter zu:
$\begin{eqnarray*} k!*(k+1)\geq 2^{(k-1)}*2^{1} \end{eqnarray*}$

Frage ist, wie ich jetzt einen gescheiten Beweis herleiten kann...
Danke für die Hilfe

21.10.2015, 18:16

mrdo87

Auf diesen Beitrag antworten »

Hallo,

Zitat:

Induktionsschritt: k->k+1
$\begin{eqnarray*} (k+1)!\geq 2^{(k+1)-1} \end{eqnarray*}$

das ist nicht wirklich der Induktionsschritt. Das ist dein "Ziel". Genau das gilt es , im Induktionsschritt zu zeigen. Du musst mit der linken Seite beginnen und diese soweit Umformen/Abschätzen und die Induktionsvorraussetzung einsetzen, bis du auf die rechte Seite kommst. Konkret kannst du so anfangen:

$\begin{eqnarray*} (k+1)!=k!\cdot (k+1) \ge \end{eqnarray*}$ "hier nun Induktionsvorschrift nutzen und danach weiter Umformen/Abschätzen"

21.10.2015, 18:17

steviehawk

Auf diesen Beitrag antworten »

RE: Vollständige Induktion einer Ungleichung
Hallo,

Der Induktionsanfang passt ja schon. Falls du $\begin{eqnarray*} 0! := 1 \end{eqnarray*}$ wie zum Beispiel bei der Taylorformel: $\begin{eqnarray*} f(x) = \sum_{k=0}^{\infty}\frac{f^{(k)}(x)}{k!} (x-x_0)^k \end{eqnarray*}$
Dann kannst du sogar so starten:

IA $\begin{eqnarray*} 0! = 1 \end{eqnarray*}$ und $\begin{eqnarray*} 2^{-1} = \frac{1}{2} < 1 \end{eqnarray*}$ passt also

IV (die hast du vergessen, die gehört aber zu einem vollständigen Beweis dazu, und danach fragst du ja scheinbar)

Es gilt als $\begin{eqnarray*} k! \geq 2^{k-1} \end{eqnarray*}$ für ein $\begin{eqnarray*} k \in \mathbb N \end{eqnarray*}$ . (Beachte, es gilt bislang nur für ein $\begin{eqnarray*} k \in \mathbb N \end{eqnarray*}$ nicht für alle, das wollen wir erst noch zeigen.

IS: (jetzt gehen wir einfach die Ungleichung von Links nach Rechts durch smile

$\begin{eqnarray*} (k+1)! = (k+1) \cdot k! \stackrel{IV}{\geq} (k+1) \cdot 2^{k-1} ... \end{eqnarray*}$

21.10.2015, 20:39

Felixkeeg

Auf diesen Beitrag antworten »

Ui, da kamen aber schnell Antworten rein, Dankeschön für die schnelle Hilfe!

Also in etwa so sollte dann die Lösung aussehen?:
Es gilt zu prüfen: $\begin{eqnarray*} k!\geq 2^{k-1} \end{eqnarray*}$
(1) Induktionsstart
$\begin{eqnarray*} k=1<br /> 1!\geq 2^{1-1} <br /> 1\geq 1 \end{eqnarray*}$ Alles klar.

(2) Induktionsvoraussetzung (habe ich vorher als selbstverständlich erachtet, der Prof hat in der Vorlesung nicht erwähnt, dass das nochmal zu verdeutlichen ist)
Gemäß (1) wird angenommen, dass $\begin{eqnarray*} k!\geq 2^{k-1} \end{eqnarray*}$ korrekt ist.

(3) Induktionsschritt (Das wäre dann, wo ich gestrauchelt habe)
k->k+1
$\begin{eqnarray*} (k+1)!=k!*(k+1) \end{eqnarray*}$
Hier muss ich dann einfach den Term in Relation zur Voraussetzung stellen, wenn ich das richtig verstanden habe?
Da angenommen wird $\begin{eqnarray*} k!\geq 2^{k-1} \end{eqnarray*}$ wird gefolgert, dass $\begin{eqnarray*} k!*(k+1)\geq 2^{k-1}*(k+1) \end{eqnarray*}$
Und jetzt einfach durch $\begin{eqnarray*} (k+1) \end{eqnarray*}$ dividieren, um wieder auf $\begin{eqnarray*} k!\geq 2^{k-1} \end{eqnarray*}$ zu kommen.

Müsste jetzt so passen, oder?

21.10.2015, 21:41

mrdo87

Auf diesen Beitrag antworten »

du musst im Induktionsschritt zeigen, dass $\begin{eqnarray*} (k+1)!\geq 2^{(k+1)-1} \end{eqnarray*}$ ist. Du sollst nicht wieder auf deine ursprüngliche IV kommen, indem du durch (k+1) dividierst...

steviehawk hat dir den Ansatz ja schon einen Schritt weiter gezeigt, als ich:

Zitat:

$\begin{eqnarray*} (k+1)! = (k+1) \cdot k! \stackrel{IV}{\geq} (k+1) \cdot 2^{k-1} ... \end{eqnarray*}$

Tipp: Überlege dir nun, wir man $\begin{eqnarray*} (k+1) \end{eqnarray*}$ abschätzen kann, wenn $\begin{eqnarray*} k \ge 1 \end{eqnarray*}$ ist.

Neue Frage »

Antworten »

Vollständige Induktion einer Ungleichung

Verwandte Themen