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\le 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\ast 0+2^0=1\le 3^0$   (1)      	   wahr
  $n=1,3\ast 1+2^1=5\le 3^1$   (3)      	   falsch
  $n=2,3\ast 2+2^2=10\le 3^2$  (9)      	  falsch
  $n=3,3\ast 3+2^3=17\le 3^3$ (27)           richtig
  $n=4,3\ast 4+2^4=28\le 3^4$ (81) 	  richtig
  $n=5,3\ast 5+2^5=47\le 3^5$ (243) 	  richtig

Dies ergibt die Vermutung, dass die Gleichung für alle $n\ge 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\ge 3$ gilt.

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

Induktionsschluß:

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

und die Gleichung ist für alle $n\ge 3$ und $n=0$ bewiesen. //Heholord fragt: Warum ist sie damit für $n\ge 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\le 3^n$

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

Die beste Vorgehensweise bei Ungleichungen ist, nicht beide Seiten gleichzeitig umzuformen, sondern eine Kette aus = und $\le$-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\ast 2^n$

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

$2^n\le 3^n-3n$

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

$3n+3+2\ast 2^n\le 3n+3+2\ast (3^n-3n)=3n+3+2\ast 3^n-2\ast 3n=2\ast 3^n+3-3n$

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

$2\ast 3^n+3-3n\le 2\ast 3^n$

Nun folgen ein paar simple Schritte:

$2\ast 3^n\le 3\ast 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 $\le$, 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

1. Induktionsanfang (IA)
2. 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\le 3^n$.

Die Ungleichung

$\begin{array}{ccccccccccc}n& L.S.& R.S.& & n& L.S.& R.S.& & n& L.S.& R.S.\\ 0& 1& 1& & 1& 5& 3& & 2& 10& 9\\ 3& 17& 27& & 4& 28& 81& & 5& 47& 243\\ 6& 82& 729& & 7& 149& 2187& & 8& 280& 6561\end{array}$

Induktionsanfang

Wir sehen, dass die Gleichung für $n=0$ und $n\ge 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 $17\le 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):=3\cdot n+2^n$ und $RS(n):=3^n$ für die beiden Seiten definieren. Der Differenzenquotient der linken Seite $LQ(n)$ bzw. der rechten $RQ(n)$ ist dann:

$LQ(n):=\frac{LS(n+1)}{LS(n)}=\frac{3\cdot (n+1)+2^{n+1}}{3\cdot n+2^n}RQ(n):=\frac{RS(n+1)}{RS(n)}=\frac{3^{n+1}}{3^n}=3$.

Induktionsvoraussetzung (IV)

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

Induktionsbehauptung

Ausgehend von der Induktionsvoraussetzung, dass die Ungleichung $3\cdot n+2^n\le 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\le 3^n⟹3\cdot (n+1)+2^{n+1}\le 3^{n+1}$.

Induktionsschritt

Wir schauen uns die linke Seite der Ungleichung an:

$\begin{array}{cc}& \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)}\le 2+\frac{3-3}{3+(2^n/n)}=2⟹\\ & ⟹LQ(n)=\frac{LS(n+1)}{LS(n)}\le 2RQ(n)=3.\end{array}$

Laut Induktionsvoraussetzung gilt $3\cdot n+2^n\le 3^n⟹LS(n+1)=3\cdot (n+1)+2^{n+1}\le 2\cdot LS(n)=2\cdot (3\cdot n+2^n)\le 3\cdot 3^n=3^{n+1}⟹3\cdot (n+1)+2^{n+1}\le 3^{n+1}$.

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

$3\cdot n+2^n\le 3^n$

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

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_21