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

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

$(n+1)3^{n}\leq 4^{n}$

(ist auch Induktionsvoraussetzung, d.h. wir gehen davon aus, dass dies eine wahre Aussage ist)

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
}}

Durch herumprobieren kommt man darauf, dass diese Ungleichung ab 8 gilt. Falls jemand weiß, wie man sie löst, kann er bitte die Lösung reinschreiben.

1.für welche n>=0 gilt die Ungleichung

Einsetzten der Zahlen und schauen ob und ab wann die Aussage wahr ist:

• $n=0:(0+1)*3^{0}\leq 4^{0},1\leq 1\Rightarrow$ Wahre Aussage
• $n=1:(1+1)*3^{1}\leq 4^{1},2*3\leq 4,6\leq 4\Rightarrow$ Falsche Aussage
• $n=2:(2+1)*3^{2}\leq 4^{2},3^{3}\leq 16,27\leq 16\Rightarrow$ Falsche Aussage
• $n=5:(5+1)*3^{5}\leq 4^{5},6*243\leq 1024,1358\leq 1024\Rightarrow$ Falsche Aussage
• $n=7:(7+1)*3^{7}\leq 4^{7},8*2187\leq 16184,27\leq 16\Rightarrow$ Falsche Aussage
• $n=8:(8+1)*3^{8}\leq 4^{8},9*6551\leq 64736,58959\leq 64736\Rightarrow$ Wahre Aussage

Ab 8 ist die Aussage wahr, wird auch für alle folgendne Zahlen so bleiben, da $4^{n}$ schneller wächst als $n3^{n}\Rightarrow$ ab 8 gilt die Ungleichung

2. der Beweis mit vollständiger Induktion

Durch das Induktionsprinzip erhalten wir die Ungleichung:
$(n+2).3^{n+1}\leq 4^{n+1}$

$(n+2).3^{n+1}\leq 4^{n}*4$

${\frac {(n+2).3^{n+1}}{4}}\leq 4^{n}$

Durch diverse Umformungen erhalten wir obige Ungleichung, wo wir auf der rechten Seite wieder eine Ausdruck haben ($4^{n}$), der in der ursprünglichen wahren Aussage vorhanden ist; das Prinzip der vollständigen Induktion wäre jetzt, die ursprüngliche Aussage einfließen zu lassen, bis wir wieder auf eine wahre Aussage kommen.

${\frac {(n+2).3.3^{n}}{4}}\leq 4^{n}$

${\frac {3}{4}}.(n+2).3^{n}\leq 4^{n}$

Weiters wissen wir die Induktionsvorraussetzung: $(n+1).3^{n}\leq 4^{n}$

Daraus folgt die Abschätzung: ${\frac {3}{4}}.(n+2).3^{n}\leq (n+1).3^{n}\leq 4^{n}$

${\frac {3}{4}}.(n+2).3^{n}\leq (n+1).3^{n}$

${\frac {3}{4}}.(n+2)\leq n+1$

${\frac {3}{4}}.n+{\frac {3}{2}}\leq n+1$

$0\leq {\frac {1}{4}}.n-{\frac {1}{2}}$

Also gilt die Behauptung für Alle n größer gleich 2! Da die Vorraussetzung erst ab n=8 gilt, stimmt die Aussage für alle n>=8

Hoffe die Weiterführung ist korrekt Mit freundlichen Grüßen Martin

Vorschlag zum Rausfinden des Induktionsanfangs:

Man kann die linke und die rechte Seite der Ungleichung als zwei Funktionen darstellen.
Dort wo sich die beiden Funktionen schneiden ergibt sich der Induktionsanfang.

- wie gesagt ist nur ein Vorschlag - Mit freundlichen Grüßen Morten

-blauerApfel: (gleich wie oben nur ohne brüche)

${\frac {(n+2)\ast 3\ast 3^{n}}{4}}\leq 4^{n}$

${\frac {(3n+6)\ast 3^{n}}{4}}\leq 4^{n}$

Weiters wissen wir die Induktionsvorraussetzung: $(n+1)\ast 3^{n}\leq 4^{n}$

Daraus folgt die Abschätzung: ${\frac {(3n+6)\ast 3^{n}}{4}}\leq (n+1)\ast 3^{n}\leq 4^{n}$

${\frac {(3n+6)\ast 3^{n}}{4}}\leq (n+1)\ast 3^{n}$

$(3n+6)\ast 3^{n}\leq 4\ast ((n+1)\ast 3^{n})$

Anmerkung (Zeile oben): die äußeren Klammern rechts sind überflüssig. Siehe nächste Anmerkung.

$(3n+6)\ast 3^{n}\leq (4n+4)\ast 4\ast 3^{n}$

Anmerkung: hier ist glaube ich ein Fehler unterlaufen. die 4 wurde hineinmultipliziert, steht aber noch immer da.

$(3n+6)\ast 3^{n}\leq (16n+16)\ast 3^{n}$

$(3n+6)\leq (16n+16)$

$0\leq (13n+10)$

q.e.d

Anmerkung: ich habe nach korrigiertem Fehler als Erbenis erhalten, dass die Ungleichung für alle n >= 2 gilt

Hilfreiches von Har203

Vollständige Induktion

Vollständige Induktion

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

Lösungsvorschlag von Har203

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

Man untersuche mittels vollständiger Induktion, für welche $n>0$ die angegebene Ungleichung gilt: $(n+1)\cdot 3^{n}\leq 4^{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&6&4&\,&2&27&16\\\hline 3&108&64&\,&4&405&256&\,&5&1458&1024\\\hline 6&5103&4096&\,&7&17496&16384&\,&8&{\color {blue}59049}&{\color {blue}65536}\\\hline 9&{\color {blue}196830}&{\color {blue}262144}&\,&10&{\color {blue}649539}&{\color {blue}1048576}&\,&11&{\color {blue}2125764}&{\color {blue}4194304}\\\hline \end{array}}$

Induktionsanfang

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

Wir beweisen die Aussage für alle $n\geq 8$ per vollständiger Induktion mit Startwert 8.

Wenn wir uns die Ungleichung anschauen, erkennen wir, dass auf der linken Seite die Werte exponentiell zur Basis 3 und auf der rechten exponentiell zur Basis 4 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 =(n+1)\cdot 3^{n}$ und $RS(n)\colon =4^{n}$ für die beiden Seiten definieren. Der Differenzenquotient der linken Seite $LQ(n)$ bzw. der rechten $RQ(n)$ ist dann:

${\begin{alignedat}{1}&{\color {green}RQ(n)\colon =}{\frac {RS(n+1)}{RS(n)}}={\frac {4^{n+1}}{4^{n}}}{\color {green}=4}.\\&{\color {green}LQ(n)\colon =}{\frac {LS(n+1)}{LS(n)}}={\frac {(n+2)\cdot 3^{n+1}}{(n+1)\cdot 3^{n}}}\end{alignedat}}$

Induktionsvoraussetzung (IV)

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

Induktionsbehauptung

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

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

Induktionsschritt

Wir schauen uns die linke Seite der Ungleichung an:

${\begin{alignedat}{1}&LQ(n)\colon &={\frac {LS(n+1)}{LS(n)}}={\frac {(n+2)\cdot 3^{n+1}}{(n+1)\cdot 3^{n}}}={\frac {(n+2)\cdot 3}{n+1}}={\frac {3\cdot (n+1)+3}{n+1}}=\\&&={\frac {3\cdot (n+1)}{n+1}}+{\frac {3}{n+1}}=3+{\frac {3}{n+1}}\quad (n\geq 8)\implies \\&&\implies {\color {green}LQ(n)\leq 3+(3/9)=10/3\approx 3,333\leq RQ(n)=4}\end{alignedat}}$

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

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

$(n+1)\cdot 3^{n}\leq 4^{n}$

• Gesamtergebnis: Die Ungleichung $(n+1)\cdot 3^{n}\leq 4^{n}$ ist für $n\in \mathbb {N} ,\,n\geq 8,$ 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:

• TU_Wien:Algebra_und_Diskrete_Mathematik_VU_(diverse)/Übungen_2025W/Beispiel_18
• TU_Wien:Algebra_und_Diskrete_Mathematik_VU_(diverse)/Übungen_2025W/Beispiel_19
• TU_Wien:Algebra_und_Diskrete_Mathematik_VU_(diverse)/Übungen_2025W/Beispiel_20