Vollstaendige Induktion mit Ungleichungen

28.12.2005, 15:59

Thomas_

Vollstaendige Induktion mit Ungleichungen

Hallo,

ja, ich habe mir die anderen (unzaehligen) Threads zu dem Thema schon angesehen, auch den Workshop. Ich denke, das Prinzip habe ich verstanden, kann es auch auf einfache Aufgaben wie $\begin{eqnarray*} 1+2+3+...+n=\frac{n*(n+1)}{2} \end{eqnarray*}$ anwenden.

Nun nochmal zu eine Aufgaben aus einem anderen Thread:

Zitat:

Aufgabe
Beweise, dass fuer $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ gilt $\begin{eqnarray*} 2n+1\leq2^{n} \end{eqnarray*}$

Induktionsanfang: n=3
$\begin{eqnarray*} 2*3+1\leq2^{3} \end{eqnarray*}$ stimmt.

Induktionsanname:
$\begin{eqnarray*} 2n+1\leq2^{n} \end{eqnarray*}$

Induktionsschluss:
$\begin{eqnarray*} 2(n+1)+1 = 2n+3 \leq 2^n +3 \leq 2^n * 2^n = 2^{n+1} \end{eqnarray*}$

Doch wie komme ich auf diesen Teil des Induktionsschlusses?
$\begin{eqnarray*} 2n+3 \leq 2^n +3 \leq 2^n * 2^n \end{eqnarray*}$

Danke im Voraus,
Thomas

28.12.2005, 16:02

JochenX

Auf diesen Beitrag antworten »

erster teil ist die induktionsvoraussetzung
2n+1<2^n
=> (2n+1)+2<(2^n)+3

zweiter teil folgt aus 2^n>3 und 2^n>=1

28.12.2005, 16:04

Auf diesen Beitrag antworten »

wie kommst du auf das $\begin{eqnarray*} 2^{n} \cdot 2^{n} \end{eqnarray*}$ ?

Da müsste doch eigentlich $\begin{eqnarray*} 2^{n+1} = 2^{n} \cdot 2 \end{eqnarray*}$ stehen, damit wärst du doch auch schon fertig.

28.12.2005, 16:05

Ben Sisko

Auf diesen Beitrag antworten »

Bei der ersten Ungleichung benutzt man $\begin{eqnarray*} 2n\leq2^n \end{eqnarray*}$ . Das gilt, da ja nach IV sogar $\begin{eqnarray*} 2n+1\leq2^n \end{eqnarray*}$ .

Bei der zweiten Ungleichung benutzt man $\begin{eqnarray*} 3\leq2^n \end{eqnarray*}$ , was ebenfalls eine schwächere Aussage ist als die IV.

Allerdings müsste dort $\begin{eqnarray*} 2^n+2^n \end{eqnarray*}$ stehen und nicht $\begin{eqnarray*} 2^n*2^n \end{eqnarray*}$ .

Gruß vom Ben

Edit: Doppelt zu langsam...

28.12.2005, 21:26

Thomas_

Auf diesen Beitrag antworten »

Tut mir Leid, das mit dem $\begin{eqnarray*} 2^n \end{eqnarray*}$ war ein Copy & Paste Fehler, es sollte $\begin{eqnarray*} 2^n * 2 \end{eqnarray*}$ heissen.

Allerdings scheine ich hier wirklich ein Brett vorm Kopf zu haben, so bloed es auch klingen mag und peinlich mir es ist: Ich sehe es immernoch nicht traurig

Wo kommt das $\begin{eqnarray*} +3 \end{eqnarray*}$ bei $\begin{eqnarray*} 2^n + 3 \end{eqnarray*}$ her bzw. wofuer ist es da? Bei einer Gleichung muss ich ja die Induktionsbehauptung in dem Schluss wieder haben, wo ist das bei der Ungleichung?

Danke,
Thomas

28.12.2005, 22:21

Ben Sisko

Auf diesen Beitrag antworten »

Hast du doch schon selbst geschrieben: $\begin{eqnarray*} 2(n+1)+1=2n+3 \end{eqnarray*}$

28.12.2005, 22:33

Thomas_

Auf diesen Beitrag antworten »

So bloed es klingt, es erklaert sich mir immernoch nicht ganz..
Mal ganz ausfuehrlich:

Induktionsschluss:
$\begin{eqnarray*} 2(n+1)+1 = 2n+3 \end{eqnarray*}$

Da $\begin{eqnarray*} 2n < 2^n \end{eqnarray*}$ :

$\begin{eqnarray*} 2n+3 \leq 2^n +3 \end{eqnarray*}$

Da $\begin{eqnarray*} 3 < 2^n \end{eqnarray*}$ :

$\begin{eqnarray*} 2^n +3 \leq 2^n + 2^n \end{eqnarray*}$

$\begin{eqnarray*} 2^n + 2^n = 2^{n+1} \end{eqnarray*}$

Sehe ich das richtig?

28.12.2005, 22:51

Thomas_

Auf diesen Beitrag antworten »

Und nochmal um sicher zu gehen:

Zitat:

Fuer welche natuerlichen Zahlen gilt $\begin{eqnarray*} n^2 \leq 2^n \end{eqnarray*}$ ?

Sagen wir $\begin{eqnarray*} A(n) = n^2 \leq 2^n \end{eqnarray*}$

Durch Ausprobieren:
A(1) = wahr
A(2) = wahr
A(3) = falsch
A(4) = wahr
A(5) = wahr

Induktionsanfang mit 4:
$\begin{eqnarray*} A(n) = 4^2 \leq 2^4 \end{eqnarray*}$ stimmt.

Induktionsannahme:
$\begin{eqnarray*} A(n) = n^2 \leq 2^n \end{eqnarray*}$ gilt.

Induktionsschluss:
$\begin{eqnarray*} (n+1)^2 = n^2 + 2n + 1 \end{eqnarray*}$

Da $\begin{eqnarray*} n^2 \leq 2^n \end{eqnarray*}$ gilt:

$\begin{eqnarray*} n^2 + 2n + 1 \leq 2^n + (2n + 1) \end{eqnarray*}$

Da $\begin{eqnarray*} 2n+1 \leq 2^n \end{eqnarray*}$ gilt:

$\begin{eqnarray*} 2^n + (2n + 1) \leq 2^n + 2^n \end{eqnarray*}$

$\begin{eqnarray*} 2^n + 2^n = 2^{n+1} \end{eqnarray*}$

Ist das richtig so?

28.12.2005, 23:01

Ben Sisko

Auf diesen Beitrag antworten »

Zitat:

Original von Thomas_
Da $\begin{eqnarray*} 2n+1 \leq 2^n \end{eqnarray*}$ gilt:

Das müsstest du noch begründen.
Ansonstens ist's ok. Auch die erste Aufgabe.

Gruß vom Ben

28.12.2005, 23:04

Thomas_

Auf diesen Beitrag antworten »

Zitat:

Original von Ben Sisko
Das müsstest du noch begründen.

Klar, ich dachte das geht hier jetzt aus der ersten Aufgabe hervor, das war ja genau diese.

Vielen Dank nochmal.

28.12.2005, 23:07

Ben Sisko

Auf diesen Beitrag antworten »

OK, HIER müsstest du es nicht begründen. Stände die Aufgabe alleine aber schon.

Gruß vom Ben

Neue Frage »

Antworten »

Vollstaendige Induktion mit Ungleichungen

Verwandte Themen