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

Aus VoWi
Zur Navigation springen Zur Suche springen

Man untersuche durch vollständige Induktion, für welche n >= 0 folgende Ungleichung gilt:

 3n + 2^n  \leq  3^{n}

SS08 Beispiel 3

Lösungsvorschlag[Bearbeiten]

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

   n = 0,	3*0 + 2^0 =   1   \leq 3^0    (1)      	   wahr
   n = 1,	3*1 + 2^1 =   5   \leq 3^1    (3)      	   falsch
   n = 2,	3*2 + 2^2 =  10  \leq 3^2    (9)      	  falsch
   n = 3,	3*3 + 2^3 =  17  \leq 3^3   (27)           richtig
   n = 4,	3*4 + 2^4 =  28  \leq 3^4   (81) 	  richtig
   n = 5,	3*5 + 2^5 =  47  \leq 3^5   (243) 	  richtig

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

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

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

Die Induktionsbehauptung: 3(n+1)+ 2^{n+1} \leq  3^{n+1}

Induktionsschluß:

 3*(n +1)+ 2^{n+1} \leq 3*(3n + 2^n )  	\leq  3^{n+1} = 3*3^n  | Term * 3
   3n +3 + 2*2^n  \leq 9*n + 3*2^n 		               | - 2*2^n, - 3*n
                  3 \leq 	6*n + 2^n	

und die Gleichung ist für alle  n \geq 3 und  n = 0 bewiesen. //Heholord fragt: Warum ist sie damit für  n \geq 3 und  n = 0 bewiesen?

Hapi

Lösungsvorschlag von Ryus[Bearbeiten]

Induktionsanfang siehe oben.

Zum Induktionsschritt:

Unsere Induktionsvoraussetzung lautet: 3n + 2^n \leq 3^n

Unsere Induktionsbehauptung lautet: 3(n+1)+2^{n+1} \leq 3^{n+1}

Die beste Vorgehensweise bei Ungleichungen ist, nicht beide Seiten gleichzeitig umzuformen, sondern eine Kette aus = und \leq-Ketten zu bilden, um so von der linken Seite auf die rechte zu kommen (siehe [1]). Wir fangen also mit der linken Seite an und formen sie ein bisschen um:

3(n+1)+2^{n+1} = 3n + 3 + 2*2^n

Wir müssen es irgendwie schaffen, unsere Induktionsvoraussetzung zu nutzen. Um dies zu schaffen, formen wir unsere Induktionsvoraussetzung etwas um:

2^n \leq 3^n - 3n

Diese umgeformte IVR können wir nun in unsere letzte Formel einsetzen und dann weiter umformen:

3n + 3 + 2*2^n \leq 3n + 3 + 2*(3^n - 3n) = 3n + 3 + 2*3^n - 2*3n = 2*3^n + 3 - 3n

Was steht hier nun? Wir haben 2*3^n, dazu wird 3 dazu addiert und 3n subtrahiert. 3n ist sicher größer als 3 (da n \geq 3 laut Induktionsanfang). Daher ist 3-3n sicher kleiner 0. Sprich wir ziehen etwas von 2*3^n ab. Lassen wir diese Subtraktion einfach weg, erhalten wir etwas, was sicher größer ist.

2*3^n + 3 - 3n \leq 2*3^n

Nun folgen ein paar simple Schritte:

2*3^n \leq 3*3^n = 3^{n+1}

Wir haben nun also eine lange Kette gebildet, auf deren linker Seite 3(n+1)+2^{n+1} steht, dann folgen lauter = bzw \leq, und am rechten Ende steht 3^{n+1}. So haben wir also die Induktionsbehauptung gezeigt und die Aussage bewiesen.

--Ryus (Diskussion) 21:58, 18. Okt. 2015 (CEST)