TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 18

Aus VoWi
Zur Navigation springen Zur Suche springen

Man untersuche mittels vollständiger Induktion, für welche n \geq 0 die angegebene Ungleichung gilt:

 9n^3 - 3 \leq 8^{n}

Lösungsvorschlag[Bearbeiten]

Als ersten Schritt untersuchen wir die Gleichung durch Einsetzen für n:

 n = 1	9*1^3 - 3 =   6  < 8^1   (8)     richtig
 n = 2	9*2^3 - 3 =  69  < 8^2  (64)    falsch
 n = 3	9*3^3 - 3 = 240  < 8^3 (512)   richtig
 n = 4	9*4^3 - 3 = 573  < 8^4 (4096)  richtig

Dies ergibt die Vermutung, daß die Gleichung für alle n \geq 3 gilt, da 8^n stärker wächst als n³.

Der Induktionsanfang für n = 3 ist bereits bewiesen.

Die Induktionsvoraussetzung, daß die Gleichung für alle n \geq 3 gilt.

Die Induktionsbehauptung: 9(n+1)^3 -3 \leq 8^{n+1}

Induktionsschluß: ACHTUNG: hier sind offensichtlich Fehler! siehe Diskussionsseite

 9*(n +1)^3-3 = 8*(9n^3- 3)  	   \leq 8^{n+1}  =  8*8^n  | Term * 8
 9*(n +1)^3  \leq 72*n^3 -21       	      |  / 9
     (n +1)^3  \leq 8n^3 - 7/3 
   n^3 +3n^2 +3n +1  \leq 8n^3 -7/3 	 | -n³
  3n^2+3n+1   \leq 7n^3 -7/3		       | Ersetzen n durch höchste Potenz
  3n^2+3n^2  \leq 7n^3 			  

und 6n² sind bei n >= 3immer kleiner als 7n³

Hapi

Lösungsvorschlag von Tonico[Bearbeiten]

IV: P(n) sei die Aussage
8n ≥ 9n3 - 3, für alle n ≥ 3.

IA: Die Aussage P(3), 83 = 512 ≥ 9·33 - 3 = 240, ist wahr.

IS: Aus P(n) folgt P(n + 1) ist gleichbedeutend mit
8·8n = 8n+1 ≥ 8·(9n3 - 3) ≥ 9(n + 1)3 - 3.

Daraus folgt, dass für alle n ≥ 3 P(n) wahr ist.

Lösung in der Übung akzeptiert[Bearbeiten]

Ungleichung: u(n) := 9n^3 - 3 \le 8^n

Erste analyse: Mittels einsetzen erhält man: Die Ungleichung gilt für n = 1, und alle n größer oder gleich 3.

Vereinfachung: Auf der linken Seite 3 addieren. Man vergrößert die Zahl, von der man annimmt, dass sie kleiner ist. Die Ungleichung u_1(n) := 9n^3 \le 8^n gilt immernoch für die angenommen n \ge 3.

Induktion: Es muss sowohl u(n), als auch u(n+1) gelten. Um eine einfache Endungleichung zu erhalten dividiert man \frac{u_1(n+1)}{u_1(n)} und erhält:

 \frac{9(n+1)^3}{9n^3} \le \frac{8^{n+1}}{8^n} | Man kürzt links durch 9n^3, rechts durch 8^n
 \frac{(n+1)^3}{n^3} \le 8 | Man zieht die 3. Wurzel
 \frac{n+1}{n} \le 2 \Rightarrow 1 + \frac{1}{n} \le 2 \Rightarrow \frac{1}{n} \le 1 | Und den Kehrwert:
 n \ge 1

Die Endungleichung ist natürlich für alle n größer oder gleich 3 gültig. Es gilt:

Wenn die durch x beschriebene Menge die angenommene Menge x größer-gleich 3 ist: \forall n \in \{x \colon x \ge 3 \} \colon n \ge 1

Wieviel das mit Induktion zu tun hat, und ob das auch wirklich anwendbar ist, weiß ich nicht.

Link zu früheren Lösungen[Bearbeiten]

TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 44