Frage zur vollständigen Induktion

09.11.2008, 21:20	BlackLabel	Auf diesen Beitrag antworten »
Frage zur vollständigen Induktion Ich bzw auch ein Großteil von meinem Kurs kapiert es noch nicht richtig. Die Aufgabe lautet : Beweise durch vollständige Induktion: Für n (gleich-größer) 5 ist n<2^n-2 Wenn man den ersten Schritt (Induktionsanfang) macht stimmt es soweit. Jetzt scheiter ich bei dem 2. Punkt mit den Induktonsschritten da muss man ja beweisen n= k+1 also: k+1 < 2^k+1-2 wie geht es aber weiter? Vielen Dank für die Antworten. und ich weiß nicht ob das zu Algebra passt. sorry wenn nicht Gruß Thomas
09.11.2008, 21:37	tigerbine	Auf diesen Beitrag antworten »
RE: Frage zur vollständigen Induktion Behauptung: $\begin{eqnarray} n < 2^{n-2}~\forall n \geq 5 \end{eqnarray}$ Beweis durch vollständige Induktion. Induktionsanfang (n=5) $\begin{eqnarray} 5 < 2^{3} = 8 \end{eqnarray}$ Induktionsvoraussetzung (IV). Die Behauptung sei richtig für n $\begin{eqnarray} n < 2^{n-2} \end{eqnarray}$ Induktionsschluss. Folgt mit der IV auch diese Gültigkeit? $\begin{eqnarray} (n+1) < 2^{(n+1)-2} = 2^{n-1}~ \end{eqnarray}$ Wie kann man nun den Term umformen, um bekanntes Wissen zu nutzen? $\begin{eqnarray} n+1 < 2^{(n-2) + 1} \end{eqnarray}$ ziehen wir das mal auseinander. $\begin{eqnarray} n+1 < 2^{(n-2)} \cdot 2 \end{eqnarray}$ Nun stellen wir das Produkt als Summe dar. $\begin{eqnarray} n+1 < 2^{n-2} + 2^{n-2} \end{eqnarray}$ Nun schätzen wir die einzelnen Summanden ab. Denkt an die IV! Es ergeben sich 2 Dinge. $\begin{eqnarray} n < 2^{n-2} \end{eqnarray}$ richtig nach IV Nun müssen wir noch die 1 abschätzen. Die ist sicherlich kleiner 5. Und damit hier auch kleiner als n. Mit einem Zwischenschritt folgt so auch aus der IV: $\begin{eqnarray} 1 <n < 2^{n-2} \end{eqnarray}$ Damit sind wir fertig. Je nach Induktionsaufgabe liegt der "Trick" anders. Ziel ist es aber immer, die IV benutzen zu können. Ich hoffe das Verfahren ist nun klarer. Weitere Beispiele: [WS] Vollständige Induktion
10.11.2008, 13:52	BlackLabel	Auf diesen Beitrag antworten »
Hey vielen dank für deine Ausfühliche Erklärung! hab alles kapiert bis auf den letzen Schritt Nun müssen wir noch die 1 abschätzen. Die ist sicherlich kleiner 5. Und damit hier auch kleiner als n. Mit einem Zwischenschritt folgt so auch aus der IV: $\begin{eqnarray} 1 <n < 2^{n-2} \end{eqnarray}$ wie kommst du darauf und wie ist damit die Behauptung bewiesen? Die Anleitung hab ich auch schon gesehen aber das kommt dieses $\begin{eqnarray} \sum_{k=1}^n~k \end{eqnarray}$ vor, mit dem ich leider nichts anfangen kann.. gruß thomas
10.11.2008, 19:45	tigerbine	Auf diesen Beitrag antworten »
In dem WS werden eben andere Beispiele gezeigt. Das Zeichen heißt Summe. Auf rechts und links stehen doch 2 Terme. Wir bilden eben Paare, um die "<" zu überprüfen. Bleibt die Frage ob gilt: $\begin{eqnarray} 1 < 2^{n-2} \end{eqnarray}$ Und da schätze ich eben nochmal ab, um dann auf bekanntes Wissen zurückgreifen zu können $\begin{eqnarray} 1 < 5 \leq n < 2^{n-2} \end{eqnarray}$
10.11.2008, 20:04	mYthos	Auf diesen Beitrag antworten »
Ich habe - ehrlich gesagt - auch eine Weile gebraucht, um bei dem Trick mit den Paaren dahinterzukommen . Ist jedoch die letzte Ungleichung nicht noch einfacher zu beweisen? Wieso nimmst du gerade die 5? Die Ungleichung gilt doch offensichtlich ab n = 3, was ist da sonst noch zu beweisen? mY+ Übrigens, Kopfzerbrechen hat mir auch der Induktionsbeweis bei Umformen bereitet. Da geht's dann vielleicht mit einem Tripel ganz gut (?)
10.11.2008, 20:17	tigerbine	Auf diesen Beitrag antworten »
Ich nehme die 5, weil die Induktion ab fünf läuft. Und sonst muss ich ja wieder argumentieren, warum die Potenzfrunktion streng monoton Steigend ist (also dass es für alle n gilt)
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »