TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 20

Man untersuche durch vollständige Induktion, für welche n >= 0 folgende Ungleichung gilt:
$3n+2^{n}\leq 3^{n}$

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

SS08 Beispiel 3

Lösungsvorschlag

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? A: wenns für 3 gilt und für den nachfolger von 3 (3+1) gilt, dann hast dus für alle ab 3 bewiesen. und 0 einsetzen

Hapi

Lösungsvorschlag von Ryus

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)

Hilfreiches von Har203

Vollständige Induktion

Vollständige Induktion

Induktionsanfang (IA)
Induktionsschritt (IS): Induktionsvoraussetzung (IV) $\Rightarrow$ Induktionsbehauptung (IB)

Lösungsvorschlag von Har203

--Har203 03:01, 21. Feb. 2026 (CET)

Man untersuche mittels vollständiger Induktion, für welche $n>0$ die angegebene Ungleichung gilt: $3\cdot n+2^{n}\leq 3^{n}$ .

Die Ungleichung

{\begin{array}{|c|c|c|l|c|c|c|l|c|c|c|}\hline n&L.S.&R.S.&\,&n&L.S.&R.S.&\,&n&L.S.&R.S.\\\hline 0&{\color {blue}1}&{\color {blue}1}&\,&1&5&3&\,&2&10&9\\\hline 3&{\color {blue}17}&{\color {blue}27}&\,&4&{\color {blue}28}&{\color {blue}81}&\,&5&{\color {blue}47}&{\color {blue}243}\\\hline 6&{\color {blue}82}&{\color {blue}729}&\,&7&{\color {blue}149}&{\color {blue}2187}&\,&8&{\color {blue}280}&{\color {blue}6561}\\\hline \end{array}}

Induktionsanfang

Wir sehen, dass die Gleichung für $n=0$ und $n\geq 3$ gelten dürfte. Daher setzen wir ausgehen von der oberen Tabelle die vollständige Induktion mit dem Anfangswert $n\in \mathbb {N}$ mit $n=3$ fest. Für den Anfangswert $n=3$ überprüfen wir die Ungleichung und erhalten ${\color {green}17}\leq {\color {green}27}$ , also ist die Ungleichung für den Anfangswert gültig.

Wenn wir uns die Ungleichung anschauen, erkennen wir, dass auf der linken Seite die Werte exponentiell zur Basis 2 und auf der rechten exponentiell zur Basis 3 wachsen. D.h., den besten Aufschluss über diese Ungleichung gibt uns der Differenzenquotient. Daher werden wir für beide Seiten den diskreten Differenzenquotienten bilden und die beiden Funktionen $LS(n)\colon =3\cdot n+2^{n}$ und $RS(n)\colon =3^{n}$ für die beiden Seiten definieren. Der Differenzenquotient der linken Seite $LQ(n)$ bzw. der rechten $RQ(n)$ ist dann:

LQ(n)\colon ={\frac {LS(n+1)}{LS(n)}}={\frac {3\cdot (n+1)+2^{n+1}}{3\cdot n+2^{n}}}\qquad RQ(n)\colon ={\frac {RS(n+1)}{RS(n)}}={\frac {3^{n+1}}{3^{n}}}=3

.

Induktionsvoraussetzung (IV)

Sei nun die Ungleichung $3\cdot n+2^{n}\leq 3^{n}$ für ein festes $n\in \mathbb {N} ,\,n\geq 3$ gültig.

Induktionsbehauptung

Ausgehend von der Induktionsvoraussetzung, dass die Ungleichung $3\cdot n+2^{n}\leq 3^{n}$ für ein festes $n$ gilt, müssen wir zeigen, dass die Ungleichung auch für $(n+1)$ gilt:

3\cdot n+2^{n}\leq 3^{n}\implies 3\cdot (n+1)+2^{n+1}\leq 3^{n+1}

.

Induktionsschritt

Wir schauen uns die linke Seite der Ungleichung an:

{\begin{alignedat}{1}&{\frac {3\cdot (n+1)+2^{n+1}}{3\cdot n+2^{n}}}={\frac {3\cdot n+3+2\cdot 2^{n}}{3\cdot n+2^{n}}}={\frac {2\cdot (3\cdot n+2^{n})}{3\cdot n+2^{n}}}+{\frac {3-3\cdot n}{3\cdot n+2^{n}}}=\\&=2\cdot {\frac {3\cdot n+2^{n}}{3\cdot n+2^{n}}}+{\frac {3-3\cdot n}{3\cdot n+2^{n}}}=2+{\frac {(3/n)-3}{3+(2^{n}/n)}}\leq 2+{\frac {3-3}{3+(2^{n}/n)}}=2\implies \\&\implies {\color {green}LQ(n)\,=}\,{\frac {LS(n+1)}{LS(n)}}{\color {green}\leq 2}\qquad {\color {blue}RQ(n)=3}.\end{alignedat}}

Laut Induktionsvoraussetzung gilt $3\cdot n+2^{n}\leq 3^{n}\implies LS(n+1)=3\cdot (n+1)+2^{n+1}\leq {\color {green}2\cdot }LS(n)={\color {green}2\cdot }(3\cdot n+2^{n})\leq {\color {blue}3\cdot }3^{n}=3^{n+1}\implies 3\cdot (n+1)+2^{n+1}\leq 3^{n+1}$ .

Ergebnis der Induktion für $n\geq 3$ gilt:

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

Gesamtergebnis: Die Ungleichung $3\cdot n+2^{n}\leq 3^{n}$ ist für $n\in \mathbb {N} ,\,n\geq 3,$ gültig. Für $n=0$ würde die Ungleichung auch gelten. $\qquad \qquad \blacksquare$

Links

Wikipedia:

Vollständige Induktion

Mathepedia:

Beispiele Ungleichungen

Ähnliche Beispiele: