Vollständige Induktion

13.11.2019, 18:17

Wolvetooth

Vollständige Induktion

Meine Frage:
Hallo!
Ich habe folgende Aufgabe:

Beweisen Sie mittels vollständiger Induktion, dass für jede natürliche Zahl n die Ungleichung gilt:

$\begin{eqnarray*} n^{2} -1 \leq 2^{n} \end{eqnarray*}$

Hinweis: Wählen Sie einen geeigneten Induktionsanfang und argumentieren Sie im Induktionsschritt mit einer Ungleichungskette. Denken Sie daran, die einzelnen Über-gänge zu begründen und jede Verwendung der Induktionsvoraussetzung explizit zu kennzeichnen. Zeigen Sie die nicht durch Ihren Induktionsbeweis abgedeckten Fälle direkt.

Meine Ideen:
Mir wurde gesagt, dass man nicht n = 0 für den Induktionsanfang benutzen kann. Deswegen habe ich zuerst den Induktionsschritt gemacht (nicht ganz), um zu wissen, wie der kleinste n sein darf. Also:

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

wobei $\begin{eqnarray*} 2^{n} \geq n^{2} - 1 \end{eqnarray*}$
Also:

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

Und daraus "gefunden" (vielleicht ist es auch falsch), dass n = 2 sein muss.

Dann habe ich erst mit der vollständige Induktion angefangen.
1) Induktionsanfang: n = 2
$\begin{eqnarray*} n^{2} -1 \leq 2^{n} \end{eqnarray*}$
$\begin{eqnarray*} 2^{2} -1 \leq 2^{2} \end{eqnarray*}$
Sollte doch gelten.

2) Induktionsvoraussetzung: $\begin{eqnarray*} \exists n \in \mathbb N \end{eqnarray*}$ für ein n > 2: $\begin{eqnarray*} n^{2} -1 \leq 2^{n} \end{eqnarray*}$

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

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

Dann komme ich nicht weiter. Es würde mich wirklich freuen, wenn jemand mir helfen würde smile

13.11.2019, 18:25

HAL 9000

Auf diesen Beitrag antworten »

Einfach mal über den Tellerrand $\begin{eqnarray*} n=0 \end{eqnarray*}$ oder $\begin{eqnarray*} n=1 \end{eqnarray*}$ schauen: Bei welchem $\begin{eqnarray*} n \end{eqnarray*}$ wird die Ungleichung denn WIRKLICH scharf, d.h., für welches $\begin{eqnarray*} n \end{eqnarray*}$ gilt tatsächlich Gleichheit in der Ungleichung? Kleiner Tipp: Es gibt so ein $\begin{eqnarray*} n \end{eqnarray*}$ , man muss einfach mal ein wenig weiter probieren...

Und dieses $\begin{eqnarray*} n \end{eqnarray*}$ nimm dann als Induktionsanfang.

P.S.: Du kriegst deinen Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ in der von dir angedachten Weise für alle $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ nämlich aus gutem Grund nicht hin. Augenzwinkern

14.11.2019, 15:08

Wolvetooth

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000 für welches $\begin{eqnarray*} n \end{eqnarray*}$ gilt tatsächlich Gleichheit in der Ungleichung?

Mit n = 3 wird die Ungleichung: $\begin{eqnarray*} n^{2} -1 \leq 2^{n} \end{eqnarray*}$
zu $\begin{eqnarray*} 8 = 8 \end{eqnarray*}$

Damit ist die:

1) Induktionsanfang: n = 3
$\begin{eqnarray*} n^{2} -1 \leq 2^{n} \end{eqnarray*}$
$\begin{eqnarray*} 2^{3} -1 \leq 2^{3} \end{eqnarray*}$

2) Induktionsvoraussetzung: $\begin{eqnarray*} \exists n \in \mathbb N \end{eqnarray*}$ für ein n > 3: $\begin{eqnarray*} n^{2} -1 \leq 2^{n} \end{eqnarray*}$

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

4) Der Induktionsschritt: $\begin{eqnarray*} (n+1)^{2} -1 \leq 2^{n +1} \end{eqnarray*}$
$\begin{eqnarray*} n^{2} +2n +1 -1 \leq 2^{n}*2^{1} \end{eqnarray*}$
$\begin{eqnarray*} n^{2}+2n \leq 2^{n} * 2 ^{1} \end{eqnarray*}$

Und dann?

PS: Ist es richtig bisher?

14.11.2019, 15:53

HAL 9000

Auf diesen Beitrag antworten »

Zunächst mal ist festzustellen, dass dieser Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ angesichts unseres nunmehr gewählten Induktionsanfangs nur für $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ funktionieren muss. Unter Nutzung der Induktionsvoraussetzung (IV) besteht dieser Induktionsschritt aus der Ungleichungskette

$\begin{eqnarray*} 2^{n+1} = 2\cdot 2^n \stackrel{IV}{\geq} 2(n^2-1) = n^2+{\color{red}n^2}-2\geq n^2+{\color{red}3n}-2 = n^2+2n+{\color{blue}n}-2\geq n^2+2n+{\color{blue}3}-2 = (n+1)^2 > (n+1)^2-1 \end{eqnarray*}$ ,

die Stellen, wo $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ genutzt wurde, habe ich farblich entsprechend markiert. Wenn du dir das Schritt für Schritt mal anschaust wirst du auch merken, dass es nur mit $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ NICHT funktioniert hätte...

14.11.2019, 17:49

Wolvetooth

Auf diesen Beitrag antworten »

Vielen Dank noch einmal für deine Antwort. Du hilfst ja sehr!

Zitat:

Original von HAL 9000

$\begin{eqnarray*} 2^{n+1} = 2\cdot 2^n \stackrel{IV}{\geq} 2(n^2-1) = n^2+{\color{red}n^2}-2\geq n^2+{\color{red}3n}-2 \end{eqnarray*}$ ,

die Stellen, wo $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ genutzt wurde, habe ich farblich entsprechend markiert. Wenn du dir das Schritt für Schritt mal anschaust wirst du auch merken, dass es nur mit $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ NICHT funktioniert hätte...

Was ich noch nicht verstehen kann, ist wie du auf: $\begin{eqnarray*} \geq n^2+{\color{red}3n}-2 \end{eqnarray*}$ kommst. Ich weiß, dass wir zeigen wollen, dass die linke Seite größer als die rechte ist, wobei wir auf der linken Seite
$\begin{eqnarray*} n^2+{\color{red}n^2}-2 \end{eqnarray*}$ haben und auf der rechten Seite $\begin{eqnarray*} n^2 +2n \end{eqnarray*}$ aus der Behauptung: $\begin{eqnarray*} (n+1)^2 - 1 \end{eqnarray*}$

Ich weiß nicht, wie du $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ angewendet hast, um weiter zu machen. Dieser Schritt verwirrt mich immer bei den Ungleichungensbeweise traurig

14.11.2019, 18:16

HAL 9000

Auf diesen Beitrag antworten »

Da hab ich es schon farblich markiert, und es war doch zu wenig...

Aus $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ folgt durch Multiplikation mit der positiven Zahl $\begin{eqnarray*} n \end{eqnarray*}$ auch $\begin{eqnarray*} n^2\geq 3n \end{eqnarray*}$ , und das dürfen wir in der Abschätzung nutzen!

14.11.2019, 19:28

Wolvetooth

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Da hab ich es schon farblich markiert, und es war doch zu wenig...

Aus $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ folgt durch Multiplikation mit der positiven Zahl $\begin{eqnarray*} n \end{eqnarray*}$ auch $\begin{eqnarray*} n^2\geq 3n \end{eqnarray*}$ , und das dürfen wir in der Abschätzung nutzen!

Ja, genau was du farblich markiert hast, ist es was ich nicht verstehen kann.

Wie sind wir aus $\begin{eqnarray*} n^2 \end{eqnarray*}$ auf $\begin{eqnarray*} 3n \end{eqnarray*}$ mit $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ gekommen? Sorry

14.11.2019, 19:56

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Wolvetooth
Wie sind wir aus $\begin{eqnarray*} n^2 \end{eqnarray*}$ auf $\begin{eqnarray*} 3n \end{eqnarray*}$ mit $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ gekommen? Sorry

Du willst mich jetzt verar...en, oder? Das habe ich doch gerade erklärt! böse

NOCHMAL ZUM MITSCHREIBEN: Der Induktionsschritt wird für alle $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ durchgeführt, und NUR FÜR DIESE $\begin{eqnarray*} n \end{eqnarray*}$ . Damit dürfen wir (und müssen es im vorliegenden Fall) auch dieses $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ bzw. daraus abgeleitete Ungleichungen in der Abschätzung nutzen, und nichts weiter habe ich dann oben gemacht.

15.11.2019, 08:38

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Wolvetooth
Ja, genau was du farblich markiert hast, ist es was ich nicht verstehen kann.

Wie sind wir aus $\begin{eqnarray*} n^2 \end{eqnarray*}$ auf $\begin{eqnarray*} 3n \end{eqnarray*}$ mit $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ gekommen? Sorry

Warum und unter welchen Bedingungen die Ungleichung $\begin{eqnarray*} n^2 \geq 3n \end{eqnarray*}$ gilt, hat HAL 9000 mühevollst erklärt. Wenn du nun in dem Term $\begin{eqnarray*} n^2 + n^2 - 2 \end{eqnarray*}$ eins der beiden n² durch das kleinere 3n ersetzt, dann gilt logischerweise: $\begin{eqnarray*} n^2 + n^2 - 2 \geq n^2 + 3n - 2 \end{eqnarray*}$ smile

18.11.2019, 15:35

Wolvetooth

Auf diesen Beitrag antworten »

Ich möchte wirklich niemanden vera....en traurig

Ich verstehe doch, warum wir nicht n $\begin{eqnarray*} \geq 2 \end{eqnarray*}$ anwenden können. (Weil sonst die Ungleichung nicht stimmen würde und mit n $\begin{eqnarray*} \geq 3 \end{eqnarray*}$ stimmt/gilt schon, mit n $\begin{eqnarray*} \geq 4 \end{eqnarray*}$ auch, usw... (n +1) )

Zitat:

Original von klarsoweit
Wenn du nun in dem Term $\begin{eqnarray*} n^2 + n^2 - 2 \end{eqnarray*}$ eins der beiden n² durch das kleinere 3n ersetzt, dann gilt logischerweise: $\begin{eqnarray*} n^2 + n^2 - 2 \geq n^2 + 3n - 2 \end{eqnarray*}$ smile

Ich verstehe dass der Term: $\begin{eqnarray*} n^2 + n^2 - 2 \end{eqnarray*}$ mit einem der beiden $\begin{eqnarray*} n^2 \end{eqnarray*}$ dieses Terms zu: $\begin{eqnarray*} n^2 + 3n - 2 \end{eqnarray*}$ wegen $\begin{eqnarray*} n^2 = 3n \end{eqnarray*}$ wird. Aber warum machen wir das, wenn trotzdem die Ungleichung gelten würde?

Ich habe es so verstanden:

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

Und deswegen habe ich gesagt, dass:

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

mit n $\begin{eqnarray*} \geq 3 \end{eqnarray*}$ schon gilt

Ich hoffe, dass ihr jetzt besser meine Frage versteht und nicht verärgert seid Tanzen

18.11.2019, 16:12

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Wolvetooth
Ich habe es so verstanden:

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

Und deswegen habe ich gesagt, dass:

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

mit n $\begin{eqnarray*} \geq 3 \end{eqnarray*}$ schon gilt

Die rot markierte Gleichheit ist für sämtliche $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ falsch, also was soll das? Erstaunt1

Das Problem bei deinem "Weg" oben ist außerdem, dass du in wilder Weise Induktionsbehauptung (die erst noch zu beweisen ist) und Induktionsvoraussetzung (die du benutzen darfst) in bunter Weise durcheinander mixt, dass am Ende kein Leser weiß: Ist das jetzt die äquivalent umgeformte Behauptung, oder wie, oder was... Vermutlich weißt du es selber nicht.

Den Weg oben mit der Ungleichungskette habe ich gewählt, weil er logisch stringent unter alleiniger Verwendung der Induktionsvoraussetzung für $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ die Induktionsbehauptung nachweist. Du bist durchaus nicht gezwungen, dass genauso zu machen, aber man sollte schon irgendwie klar und deutlich erkennen, dass du hier die Induktionsbehauptung nachweist statt sie nur irgendwie umzuformen und was in nicht erklärter Weise "einzusetzen".

19.11.2019, 08:31

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Wolvetooth
Ich verstehe dass der Term: $\begin{eqnarray*} n^2 + n^2 - 2 \end{eqnarray*}$ mit einem der beiden $\begin{eqnarray*} n^2 \end{eqnarray*}$ dieses Terms zu: $\begin{eqnarray*} n^2 + 3n - 2 \end{eqnarray*}$ wegen $\begin{eqnarray*} n^2 = 3n \end{eqnarray*}$ wird. Aber warum machen wir das, wenn trotzdem die Ungleichung gelten würde?

Vielleicht hast du da einen Schreibfehler (oder einen weiteren Denkfehler) gemacht, aber an keiner Stelle wurde von HAL 9000 oder von mir behauptet, daß $\begin{eqnarray*} n^2 = 3n \end{eqnarray*}$ gilt. Wir haben lediglich aus n >= 3 die Ungleichung $\begin{eqnarray*} n^2 \geq 3n \end{eqnarray*}$ gefolgert. Aus dieser Ungleichung wiederum folgt die Ungleichung $\begin{eqnarray*} n^2 + n^2 - 2 \geq n^2 + 3n - 2 \end{eqnarray*}$ .

Generell solltest du einen Beweis klar strukturieren:
- was ist die Voraussetzung?
- was ist die Behauptung?
- in welchem Zusammenhang stehen die Umformungen?

Auch wenn es leider mehr oder weniger gängige Praxis ist, Gleichungen oder Ungleichungen kommentarlos untereinander zu schreiben, es fördert in keinster Weise die Lesbarkeit.

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen