Aufgabe zu einer vollständigen Induktion

02.11.2010, 17:14

bandchef

Aufgabe zu einer vollständigen Induktion

Hi Leute!

Ich hab folgende Aufgabe zur vollständigen Induktion zu lösen:

Behauptung:

$\begin{eqnarray*} 2n+1 \leq 2^n \end{eqnarray*}$ für $\begin{eqnarray*} n \geq 3, n \in \mathbb N \end{eqnarray*}$

Beweis:

(IA) n=3: $\begin{eqnarray*} 2 \cdot 3 + 1 \stackrel{!}{\leq} 2^3 \Leftrightarrow 7 \leq 8 \end{eqnarray*}$

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

Ab hier weiß ich dann leider nicht mehr weiter wie ich hier umformen muss. Könnt ihr mir weiterhelfen?

02.11.2010, 17:19

Q-fLaDeN

Auf diesen Beitrag antworten »

Fang doch einfach mal an umzuformen:

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

verwende nun die Induktionsvoraussetzung.

02.11.2010, 17:25

bandchef

Auf diesen Beitrag antworten »

Ich hab jetzt das da stehen:

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

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

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

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

Jetzt könnte ich durch 2 teilen, was mir aber nicht viel bringen wird, oder?

02.11.2010, 17:27

bandchef

Auf diesen Beitrag antworten »

Meine Induktionsvoraussetzung ist doch das: $\begin{eqnarray*} 2n+1 \leq 2^n \end{eqnarray*}$ für $\begin{eqnarray*} n \geq 3, n \in \mathbb N \end{eqnarray*}$

Wie soll ich diese Voraussetzung nun auf meine Umformung anwenden?

02.11.2010, 17:34

bandchef

Auf diesen Beitrag antworten »

Wenn ich mir nun diese umgeformte Zeile anschaue, $\begin{eqnarray*} (2n+1)+2 \leq 2^{n+1} \end{eqnarray*}$ , dann fällt mir auf, dass ich von der rechten Seite der Induktionsvoraussetzung $\begin{eqnarray*} (2n+1) \end{eqnarray*}$ plus einen zusätzlichen Anteil $\begin{eqnarray*} +2 \end{eqnarray*}$ dastehen hab. Von der rechten Seite hab ich nun anstatt $\begin{eqnarray*} 2^n \end{eqnarray*}$ , $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ dastehen.

Wenn ich nun weiter die Aufgabe betrachte, dann kann dabei nur vorkommen, dass die linke Seite für $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ kleiner oder gleich der rechten Seite ist.

Darf man das dann einfach so hinschreiben, dass es eben keine Werte gibt für die dieses Bedingung nicht erfüllt wäre?

02.11.2010, 17:38

Q-fLaDeN

Auf diesen Beitrag antworten »

Nein, so darfst du das nicht machen. Wenn du von Anfang an hinschreibst

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

dann tust du ja schon so, als sei das richtig. Aber du willst doch eben zeigen, dass das richtig ist.

Mach bei meiner Umformung weiter. Zum Verständnis: Du musst so lange umformen, bis am Ende $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ da steht. Das heißt

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

Deine Aufgabe ist es dann, die Punkte auszufüllen. In nächsten Schritt solltest du erstmal die Induktionsvoraussetzung anwenden. Wie man die Voraussetzung anwendet sollte doch eig. klar sein.

Beispiel:

Du weißt, dass $\begin{eqnarray*} a < b \end{eqnarray*}$ ist. Das sei mal deine Inkduktionsvorausetzung.

Nun willst du den Ausdruck

$\begin{eqnarray*} a+c+d \end{eqnarray*}$

mit Hilfe der IV weiter umformen. Da du weißt, dass $\begin{eqnarray*} a < b \end{eqnarray*}$ ist, gilt dann eben auch

$\begin{eqnarray*} a+c+d < b+c+d \end{eqnarray*}$

02.11.2010, 17:52

bandchef

Auf diesen Beitrag antworten »

Du schreibst:

Zitat:

Mach bei meiner Umformung weiter. Zum Verständnis: Du musst so lange umformen, bis am Ende $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ da steht. Das heißt $\begin{eqnarray*} 2(n+1)+1 = (2n+1) + 2 \leq ... \leq ... = 2^{n+1} \end{eqnarray*}$

Ich verstehe nun deine Antwort so, als soll die linke Seite nach der korrekten Umformung GLEICH dem $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ sein. Stimmt das?

02.11.2010, 18:03

Q-fLaDeN

Auf diesen Beitrag antworten »

Nein, da steht doch ein kleiner-gleich dazwischen verwirrt

Du sollst ja auch zeigen

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

und nicht

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

Vergess am besten erstmal das = am Ende. Das kann ich dir dann noch erklären wenn wir fertig sind Augenzwinkern

02.11.2010, 18:07

bandchef

Auf diesen Beitrag antworten »

Ich hab jetzt nochmal voller Elan :-) weiter gemacht und dabei auf das gestoßen:

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

Ich hab da quasi auf beiden Seiten mit $\begin{eqnarray*} (2n+1) \end{eqnarray*}$ erweitert. Ich kann mir aber nicht vorstellen, dass das irgendwie richtig ist. Ich tappe echt im Dunkeln, ich weiß nicht mehr was ich da noch umformen soll...

02.11.2010, 18:10

Q-fLaDeN

Auf diesen Beitrag antworten »

Du ignorierst irgendwie das, was ich sage. Ich zitiere mich mal selbst

Zitat:

Original von Q-fLaDeN
Nein, so darfst du das nicht machen. Wenn du von Anfang an hinschreibst

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

dann tust du ja schon so, als sei das richtig. Aber du willst doch eben zeigen, dass das richtig ist.

und genau das hast du gerade schon wieder gemacht. Du sollst hier den nächsten Schritt machen

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

und zwar mit der Induktionsvoraussetzung, wie das geht hab ich an einem Beispiel erklärt.

02.11.2010, 18:14

bandchef

Auf diesen Beitrag antworten »

Meine Induktionsvoraussetzung ist doch: $\begin{eqnarray*} 2n+1 \leq 2^n \end{eqnarray*}$ für $\begin{eqnarray*} n \geq 3, n \in \mathbb N \end{eqnarray*}$ oder?

Ich ignoriere nicht das was du schreibst sondern verstehe es vielmehr nicht.

Du schreibst ich soll die Punkte ersetzen. Das hab ich unten nun gemacht:

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

02.11.2010, 18:17

Q-fLaDeN

Auf diesen Beitrag antworten »

Das ist doch schonmal besser. Ja das ist die IV.

Nunja, du hast sie zwar eingesetzt, aber nicht richtig. Es müsste lauten

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

Verstehst du warum?

02.11.2010, 18:21

bandchef

Auf diesen Beitrag antworten »

Ich habe nun den nächsten Schritt mit der IV, $\begin{eqnarray*} 2n+1 \leq 2^n \end{eqnarray*}$ für $\begin{eqnarray*} n \geq 3, n \in \mathbb N \end{eqnarray*}$ , gemacht. Hier lautet die rechte Seite vom kleiner-gleich $\begin{eqnarray*} 2^n \end{eqnarray*}$ .

Warum ich dann bei der Aufgabe anstatt $\begin{eqnarray*} 2^n \end{eqnarray*}$ , $\begin{eqnarray*} 2^n+2 \end{eqnarray*}$ einsetzen muss weiß ich nicht. Was ich mir aber denken kann, ist, dass es irgendwie mit deinem Beispiel zusammenhängt. Die Gemeinsamkeit erkenne ich leider ebenfalls nicht...

02.11.2010, 18:26

bandchef

Auf diesen Beitrag antworten »

Ah ich glaube jetzt hab ich wieder ein Puzzle-Teilchen gefunden.

Das +2 auf der rechten Seite kommt daher weil auf der linken Seite jetzt nach der ersten Umformung auch ein +2 steht. Stimmts?

02.11.2010, 18:30

Q-fLaDeN

Auf diesen Beitrag antworten »

Erstmal: Es gibt keinen "nächsten Schritt der Induktionsvoraussetzung". Das ist einfach nur eine Voraussetzung, die man verwenden muss, um zum Ziel zu gelangen.

Ich wüsste gerade nicht wie ich das noch besser erklären kann.

Also, letztendlich will man ja zeigen, dass unter der Voraussetzung, dass wenn $\begin{eqnarray*} 2n+1 \leq 2^n \end{eqnarray*}$ für ein festes $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ wahr ist, auch $\begin{eqnarray*} 2(n+1)+1\leq 2^{n+1} \end{eqnarray*}$ wahr ist. Dazu muss man eben eine Seite so lange umformen, bis man die andere enthält. Wir haben hier eben die linke genommen und angefangen umzuformen.

$\begin{eqnarray*} 2(n+1)+1 = \underbrace{(2n+1)}_{\leq 2^n~\text{wegen der IV}} + 2 \leq 2^n + 2 \end{eqnarray*}$

Klingelts jetzt?

\Edit: Ja genau daher kommt die +2.

02.11.2010, 18:31

bandchef

Auf diesen Beitrag antworten »

Ich hab jetzt auf meinem Zettel folgenden Ablauf stehen:

(IV)
$\begin{eqnarray*} 2n+1 \leq 2^n \end{eqnarray*}$ für $\begin{eqnarray*} n \geq 3, n \in \mathbb N \end{eqnarray*}$

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

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

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

02.11.2010, 18:34

Q-fLaDeN

Auf diesen Beitrag antworten »

Und zum 3. mal machst du den Fehler, auf den ich dich nun schon, logischerweise, zum 3. mal aufmerksam mache unglücklich

Mal ganz abgesehen davon, dass bei dir auf der rechten Seite plötzlich $\begin{eqnarray*} 2^n + 2 \end{eqnarray*}$ anstatt $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ steht.

02.11.2010, 18:35

bandchef

Auf diesen Beitrag antworten »

Warum ich nun auf der rechten Seite $\begin{eqnarray*} 2^n +2 \end{eqnarray*}$ schreiben soll ist mir einerseits klar (wegen der umgeformten linken Seite), aber andererseits verstehe ich jetzt nicht mehr aus welchen Gründen man das vorherige $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ zu $\begin{eqnarray*} 2^n +2 \end{eqnarray*}$ verändern darf. Oder horchen solche Induktionsaufgaben nicht auf diese algebraischen Regeln?

02.11.2010, 18:37

bandchef

Auf diesen Beitrag antworten »

Ich glaube mein Fehler liegt bei der Notation des ganzen... Ich schreibe für gewöhnlich Sachen untereinander.

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

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

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

Jetzt stimmts wieder, oder? Und wie komme ich jetzt von dieser Zeile nach: $\begin{eqnarray*} (2n+1)+2 \leq 2^n+2 \end{eqnarray*}$ ?

Edit: Vergiss mal bitte den Beitrag von 18:35 Uhr

02.11.2010, 18:45

Q-fLaDeN

Auf diesen Beitrag antworten »

Jetzt machst du schon zum 4.(!!) mal den Fehler! Das kann doch nicht sein...

Indem du anfängst du schreiben

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

hast du schon VORAUSGESETZT, dass das stimmt, aber du willst es doch ZEIGEN!

Wir waren doch schon so weit

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

und plötzlich wirfst du alles wieder über den Haufen verwirrt

02.11.2010, 18:48

bandchef

Auf diesen Beitrag antworten »

So lange ich den gleichen Fehler immer wieder mache habe ich anscheinend ein prägnante Intention dieser vollständigen Induktion noch nicht verstanden.

Nochmal von vorne:

Ich habe eine (IV): $\begin{eqnarray*} 2n+1 \leq 2^n \end{eqnarray*}$

In dieser (IV) ersetze ich "n" mit "n+1": $\begin{eqnarray*} 2(n+1)+1 \leq 2^{n+1} \end{eqnarray*}$

Stimmt das so oder ist das schon fehlerhaft?

02.11.2010, 18:50

Q-fLaDeN

Auf diesen Beitrag antworten »

Ja das stimmt, aber vllt. ein bisschen unglücklich formuliert.

Du willst eben unter der Induktionsvoraussetzung zeigen, dass, falls diese gilt, auch $\begin{eqnarray*} 2(n+1)+1 \leq 2^{n+1} \end{eqnarray*}$ gilt.

Logisch ausgedrückt: Du musst zeigen: $\begin{eqnarray*} A(n) \Rightarrow A(n+1) \end{eqnarray*}$ wobei $\begin{eqnarray*} A(n) \end{eqnarray*}$ die zu beweisende Aussage ist.

02.11.2010, 18:57

bandchef

Auf diesen Beitrag antworten »

Ah ich glaube jetzt hab ich das bei der Aufgabe geschnallt:

Ich hab die rechte Seite der IV:

$\begin{eqnarray*} 2(n+1)+1=(2n+1)+2 \leq \underbrace{2^n}_{=IV} \underbrace{+2}_{=rS} \end{eqnarray*}$ rS = rechte Seite

02.11.2010, 18:59

bandchef

Auf diesen Beitrag antworten »

Fängt man dann bei Gleichungen an denen eine vollst. Induktion gezeigt werden soll immer mit der linken Seite an und setzt dann auf der rechten Seite eine "gleichwertige" IV ein?

Wie gehts jetzt weiter?

02.11.2010, 19:00

bandchef

Auf diesen Beitrag antworten »

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

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

Womit jetzt die vollst. Induktion bewiesen wäre, oder?

02.11.2010, 19:04

bandchef

Auf diesen Beitrag antworten »

Kannst du mir (wenn du Lust hast) vielleicht eine ähnliche (vielleicht eine etwas schwerer Aufgabe) Aufgabe stellen an der ich Überprüfen kann ob ich es komplett verstanden habe?

02.11.2010, 19:05

Q-fLaDeN

Auf diesen Beitrag antworten »

Da du anscheinend noch nicht so viel verstanden hast, erstmal eins: Les dir das alles nochmal durch, im Internet, in Büchern, wo auch immer (wenn du willst kann ich dir auch mal mein Fachreferat über die VI schicken, das ist denke ich recht kurz und bündig). Und deshalb zeig ich dir mal wie es geht:

Ich forme einfach so um:

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

Wenn du dir jetzt den Anfang und das Ende anschaust steht da nichts anderes als

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

und genau das war zu zeigen.

Nochwas:
1. Es gibt einen "Edit"-Button, den kannst du benutzen anstatt immer diese Mehrfachposts...
2. "Womit jetzt die vollständige Induktion bewiesen wäre" - du willst doch nicht das Prinzip der VI beweisen, sonsdern du versuchst eine Aussage MIT HILFE eben dieser zu beweisen.
3. Nein man kann auch rechts anfangen, wie ich schonmal gesagt habe.
4. Das was du da zusammen gemixt hast ist leider keineswegs richtig.

02.11.2010, 19:14

bandchef

Auf diesen Beitrag antworten »

Dieses Referat kannst du mir gerne schicken. Ansonsten werde ich mich heute nicht mehr dazu melden. Morgen vielleicht wieder oder evtl. zu einer anderen Aufgabe. Ist jetzt mein Beitrag von 19:00 Uhr richtig?

02.11.2010, 19:25

Q-fLaDeN

Auf diesen Beitrag antworten »

Wie schon gesagt, das war leider alles andere als richtig.
Für das Referat siehe PN.

02.11.2010, 19:53

bandchef

Auf diesen Beitrag antworten »

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

Das zweite Größer-Gleich in deiner Umformung bezieht sich auf direkt das (bis zum ersten Größer-Gleich) was hinter dem zweiten Größer-Gleich steht, oder?

darf ich dann auch so schreiben:

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

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

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

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

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

02.11.2010, 20:22

Q-fLaDeN

Auf diesen Beitrag antworten »

Das sind kleiner gleich Zeichen... und ja, die Zeichen beziehen sich immer auf das, was jeweils dahinter steht.

Du könntest das auch so schreiben, aber dadurch wird deine Argumentation nicht so wirklich schlüssig, außerdem ist es doch mehr schreibaufwand.

03.11.2010, 20:43

bandchef

Auf diesen Beitrag antworten »

Ich hab das jetzt soweit verstanden:

Ich form die anfängliche linke Seite zu dem hier um:

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

Die richtige Seite ist mir auch klar, diese 2 muss hin, damits mit der anderen Seite übereinstimmt, aber wie und warum das dann zu dem hier wird ist mir ein rätsel:

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

Welcher Gedanke steht bei dir da dahinter, dass man $\begin{eqnarray*} 2^n + 2 \leq 2^n + 2^n \end{eqnarray*}$ schreiben darf? Gut jetzt kann man sagen: "Weil es so ist" aber wie kommst du drauf?

03.11.2010, 21:17

Q-fLaDeN

Auf diesen Beitrag antworten »

Zitat:

Original von bandchef
Die richtige Seite ist mir auch klar, diese 2 muss hin, damits mit der anderen Seite übereinstimmt

Naja, übereinstimmen würde ich so nicht sagen, denn da steht ja immernoch ein kleiner gleich Zeichen dazwischen, und kein ist gleich. Achja, und von einer "richtigen Seite" kann man hier auch nicht sprechen, sowas gibt es da nicht.

Zum anderen:
Das ist eine Abschätzung. Wenn du zunächst beweisen bzw. nachvollziehen willst, warum diese gilt, dann z. B. wie folgt:

Man nehme die Ungleichung

$\begin{eqnarray*} 1 \leq n \end{eqnarray*}$ (Diese ist auf jeden Fall richtig, erst recht in diesem Beispiel)

man schiebt anschließend eine 2 unter

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

und addiert auf beiden Seiten $\begin{eqnarray*} 2^n \end{eqnarray*}$

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

und schon ist man fertig.

Neue Frage »

Antworten »

Aufgabe zu einer vollständigen Induktion

Verwandte Themen