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

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

$4n^2\le 2^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
}}

Lösung laut Prof. Pannholzer

1.) Es ist trivial zu erkennen, dass 2^n ab einem gewissen n stärker steigt als irgendwas hoch 2.

2.) Wir machen für die niedrigen Zahlen eine Tabelle um herauszufinden bei welchem n die Ungleichung gilt.

n	links	rechts	zutreffend?
0	$4\ast 0^2=0$	$2^0=1$	JA!!!
1	$4\ast 1^2=4$	$2^1=2$	NEIN!
2	$4\ast 2^2=16$	$2^2=4$	NEIN!
3	$4\ast 3^2=36$	$2^3=8$	NEIN!
4	$4\ast 4^2=64$	$2^4=16$	NEIN!
5	$4\ast 5^2=100$	$2^5=32$	NEIN!
6	$4\ast 6^2=144$	$2^6=64$	NEIN!
7	$4\ast 7^2=196$	$2^7=128$	NEIN!
8	$4\ast 8^2=256$	$2^8=256$	JA!!!
9	$4\ast 9^2=324$	$2^9=512$	JA!!!

3.) Behauptung: Die Ungleichung gilt für $n=0$ und $n\ge 8$. Das ist zu beweisen.

4.) $n=0$: Das ist bereits bewiesen (siehe Tabelle)

5.) $n\ge 8$ : Das müssen wir noch beweisen. Wir machen eine eigene Induktion, um unsere Haupt-Induktion zu lösen...

Induktionsanfang: $n=8$. Ist Bewiesen (siehe Tabelle).

Induktionsbehauptung: $n+1$:

$4\ast (n+1{)}^2\le 2^{n+1}$ umgewandelt heißt das:

$4\ast (n^2+2n+1)\le 2\ast 2^n$ weiter umgewandelt:

$4n^2+8n+4\le 2\ast 2^n$ das Ganze durch 2 dividiert:

$2n^2+4n+2\le 2^n$ (*) Diese Stelle merken wir uns.

Wir lösen jetzt ein paar triviale Nebenrechnungen:

$4\ast n\le n^2$ für $n\ge 4$ und ausserdem:

$2\le n^2$ für $n\ge 2$

Daraus folgt:

auch für $n\ge 8$ gilt

$4\ast n\le n^2$ UND

$2\le n^2$

Zurück zu unserer eigentlichen Ungleichung (*):

$2n^2+4n+2\le 2^n$ Durch einsetzen aus unseren Nebenrechnungen erhalten wir:

$2n^2+4n+2\le 2\ast n^2+n^2+n^2\le 2^n$ Wir lassen das linkeste wegfallen und vereinfachen:

$4\ast n^2\le 2^n$

Q.E.D.

Lösung mithilfe von ÖMO-Wiki

Die Richtigkeit ist (war) im Forum umstritten. Habe mich heute in der Übung zu diesem Beispiel an die Tafel gemeldet und genauso vorgerechnet... Und es hat auch gestimmt ;-) mfg LeoBlaid

Induktionsanfang: Wir müssen zuerst prüfen, ab welchem $n\ge 0$ die Ungleichung überhaupt Geltung besitzt:

n	links	rechts	zutreffend?
0	$4\ast 0^2=0$	$2^0=1$	JA!!!
1	$4\ast 1^2=4$	$2^1=2$	NEIN!
2	$4\ast 2^2=16$	$2^2=4$	NEIN!
3	$4\ast 3^2=36$	$2^3=8$	NEIN!
4	$4\ast 4^2=64$	$2^4=16$	NEIN!
5	$4\ast 5^2=100$	$2^5=32$	NEIN!
6	$4\ast 6^2=144$	$2^6=64$	NEIN!
7	$4\ast 7^2=196$	$2^7=128$	NEIN!
8	$4\ast 8^2=256$	$2^8=256$	JA!!!
9	$4\ast 9^2=324$	$2^9=512$	JA!!!

Somit gilt die Ungleichung ab $n=8$ (was noch zu beweisen ist)!

Induktionsvorraussetzung: Es muss gezeigt werden, dass gilt:

$4\ast (n+1{)}^2\le 2^{n+1}$

Wir formen

$4\ast (n+1{)}^2\le 2^{n+1}$

um zu

$4\ast (n+1{)}^2\le 2\ast 2^n$

und kürzen durch 2

$2\ast (n+1{)}^2\le 2^n$

Da bereits $4n^2\le 2^n$ gilt (siehe Angabe = Induktionsvoraussetzung), dürfen wir statt $2^n$ einsetzen (wir ersetzen in der größeren Seite der Ungleichung etwas durch etwas Kleineres -> sprich wenn die Ungleichung mit diesem kleinern Term noch immer stimmt, dann mit dem alten (größeren) Term erst recht!):

$2\ast (n+1{)}^2\le 4n^2$

Wieder durch 2 kürzen und ausquadrieren

$n^2+2n+1\le 2n^2$

und beide Glieder zusammen ergibt (= Auf beiden Seiten minus dem linken Term rechnen = Also auf beiden Seiten $-n^2-2n-1$)

$0\le n^2-2n-1$

Und schließlich noch auf ein vollständiges Quadrat ergänzen (auf beiden Seiten + 2)

$2\le n^2-2n+1$

und zusammenfassen:

$2\le (n-1{)}^2$

Daraus folgt dann, dass die vollständige Induktion für alle n größer 3 gelten würde.

Da unser Induktionsanfang (n0) aber erst bei 8 ist, gilt sie erst ab n größergleich 8. (siehe Skriptum S.3 "Bemerkung" - Punkt 2)

Ähnliches Bsp.: http://www.oemo.at/wiki/index.php?namespace=E-Kurs&title=vollst%E4ndige+Induktion --Mnemetz 06:30, 3. Nov 2005 (CET)

Überarbeitet von --LeoBlaid 00:41, 5. Nov 2005 (CET)

Lösung mittels Zwischeninduktion von Ryus

Induktionsanfang siehe oben.

Unsere Induktionsbehauptung lautet:

$4(n+1{)}^2\le 2^{n+1}$

Wie immer bei Ungleichungen fangen wir bei einer Seite an, und versuchen diese so lange zu bearbeiten, bis es offensichtlich ist, dass sie kleiner oder größer (-gleich) der anderen Seite ist.

Wir fangen also damit an, die Klammer auf der linken Seite aufzulösen:

$4(n+1{)}^2=4(n^2+2n+1)=4n^2+8n+4$

An dieser Stelle können wir die Induktionsvoraussetzung anwenden. Diese lautet bekanntlich $4n^2\le 2^{n+1}$. Daher muss also auch gelten:

$4n^2+8n+4\le 2^n+8n+4$

Soweit so gut. Nun müssen wir irgendwie zeigen, dass $2^n+8n+4\le 2^{n+1}$ ist. Wenn wir das schaffen, ist unser Induktionsschritt und damit die ganze Induktion fertig.

Um diese Aussage zu beweisen, verwende ich eine Zwischeninduktion. Beim Induktionsanfang beginne ich gleich bei 8, da die Zahlen darunter uns sowieso egal sind, da sie für die ursprüngliche Induktion sowieso nicht gelten. Wichtig ist, dass die Aussage für 8 und höher gilt. Setzt man also 8 in $2^n+8n+4\le 2^{n+1}$ ein erhält man:

$2^8+8\ast 8+4=324\le 2^9=512$

Diese Aussage ist wahr, und damit geht's weiter zum Induktionsschritt.

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

Wir fangen also wieder an, die linke Seite umzuformen:

$2^{n+1}+8(n+1)+4=2^{n+1}+8n+8+4=2^{n+1}+8n+12=2\ast 2^n+8n+12$

Hier können wir unsere Induktionsvoraussetzung verwenden. Diese lautet bekanntlich:

$2^n+8n+4\le 2^{n+1}$

Formen wir diese um, erhalten wir:

$2^n\le 2^{n+1}-8n-4$

Dies lässt sich wieder einsetzen:

$2\ast 2^n+8n+12\le 2\ast (2^{n+1}-8n-4)+8n+12=2^{n+2}-16n-8+8n+12=2^{n+2}-8n+4$

Wichtig: Da n laut Induktionsanfang größergleich 8 ist, ist 8n sicher größer als 4. Das heißt hier wird von 2^(n+2) etwas abgezogen, da -8n+4 sicher kleiner 0 ist.

Versteht man dies, folgt ganz offensichtlich:

$2^{n+2}-8n+4\le 2^{n+2}$

Damit war die Zwischeninduktion erfolgreich und wir können in unserer Ursprungsinduktion also den letzten Schritt machen:

$2^n+8n+4\le 2^{n+1}$

Was zu zeigen war.

--Ryus (Diskussion) 15:35, 11. Sep. 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 01:03, 21. Feb. 2026 (CET)

Man untersuche mittels vollständiger Induktion, für welche $n>0$ die angegebene Ungleichung gilt: $4\cdot n^2\le 2^n$.

Die Ungleichung

$\begin{array}{ccccccccccc}n& L.S.& R.S.& & n& L.S.& R.S.& & n& L.S.& R.S.\\ 0& 0& 1& & 1& 4& 2& & 2& 16& 4\\ 3& 36& 8& & 4& 64& 16& & 5& 100& 32\\ 6& 144& 64& & 7& 196& 128& & 8& 256& 256\\ 9& 324& 512& & 10& 400& 1024& & 11& 484& 2048\end{array}$

Induktionsanfang

Wir sehen, dass die Gleichung für $n=0$ und $n\ge 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 $256\le 256$, 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 zum Quadrat und auf der rechten exponentiell 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):=4\cdot n^2$ und $RS(n):=2^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{4\cdot (n+1{)}^2}{4\cdot n^2}RQ(n):=\frac{RS(n+1)}{RS(n)}=\frac{2^{n+1}}{2^n}=2$.

Induktionsvoraussetzung (IV)

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

Induktionsbehauptung

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

$4\cdot n^2\le 2^n⟹4\cdot (n+1{)}^2\le 2^{n+1}$.

Induktionsschritt

Wir schauen uns die linke Seite der Ungleichung an:

• Anmerkung: $4\cdot (n+1{)}^2=(4\cdot n^2)+(8\cdot n+4)$

$\begin{array}{cc}& \frac{4\cdot (n+1{)}^2}{4\cdot n^2}=\frac{(4\cdot n^2)+(8\cdot n+4)}{4\cdot n^2}=\frac{n^2+2\cdot n+1)}{n^2}=\frac{n^2}{n^2}+\frac{2\cdot n+1}{n^2}=\\ & =1+\frac{2+(1/n)}{n}\le 1+\frac{2+1}{n}(n\ge 8)\le 1+\frac{3}{8}=\frac{11}{8}.\\ & ⟹LQ(n)=\frac{LS(n+1)}{LS(n)}\le \frac{11}{8}RQ(n)=2.\end{array}$

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

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

$4\cdot n^2\le 2^n$

• Gesamtergebnis: Die Ungleichung $4\cdot n^2\le 2^n$ ist für $n\in \mathbb{N},n\ge 8,$ 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_20
• TU_Wien:Algebra_und_Diskrete_Mathematik_VU_(diverse)/Übungen_2025W/Beispiel_21