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

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

$4n^{2}\leq 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*0^{2}=0$	$2^{0}=1$	JA!!!
1	$4*1^{2}=4$	$2^{1}=2$	NEIN!
2	$4*2^{2}=16$	$2^{2}=4$	NEIN!
3	$4*3^{2}=36$	$2^{3}=8$	NEIN!
4	$4*4^{2}=64$	$2^{4}=16$	NEIN!
5	$4*5^{2}=100$	$2^{5}=32$	NEIN!
6	$4*6^{2}=144$	$2^{6}=64$	NEIN!
7	$4*7^{2}=196$	$2^{7}=128$	NEIN!
8	$4*8^{2}=256$	$2^{8}=256$	JA!!!
9	$4*9^{2}=324$	$2^{9}=512$	JA!!!

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

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

5.) $n\geq 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*(n+1)^{2}\leq 2^{n+1}$ umgewandelt heißt das:

$4*(n^{2}+2n+1)\leq 2*2^{n}$ weiter umgewandelt:

$4n^{2}+8n+4\leq 2*2^{n}$ das Ganze durch 2 dividiert:

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

Wir lösen jetzt ein paar triviale Nebenrechnungen:

$4*n\leq n^{2}$ für $n\geq 4$ und ausserdem:

$2\leq n^{2}$ für $n\geq 2$

Daraus folgt:

auch für $n\geq 8$ gilt

$4*n\leq n^{2}$ UND

$2\leq n^{2}$

Zurück zu unserer eigentlichen Ungleichung (*):

$2n^{2}+4n+2\leq 2^{n}$ Durch einsetzen aus unseren Nebenrechnungen erhalten wir:

$2n^{2}+4n+2\leq 2*n^{2}+n^{2}+n^{2}\leq 2^{n}$ Wir lassen das linkeste wegfallen und vereinfachen:

$4*n^{2}\leq 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\geq 0$ die Ungleichung überhaupt Geltung besitzt:

n	links	rechts	zutreffend?
0	$4*0^{2}=0$	$2^{0}=1$	JA!!!
1	$4*1^{2}=4$	$2^{1}=2$	NEIN!
2	$4*2^{2}=16$	$2^{2}=4$	NEIN!
3	$4*3^{2}=36$	$2^{3}=8$	NEIN!
4	$4*4^{2}=64$	$2^{4}=16$	NEIN!
5	$4*5^{2}=100$	$2^{5}=32$	NEIN!
6	$4*6^{2}=144$	$2^{6}=64$	NEIN!
7	$4*7^{2}=196$	$2^{7}=128$	NEIN!
8	$4*8^{2}=256$	$2^{8}=256$	JA!!!
9	$4*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*(n+1)^{2}\leq 2^{n+1}$

Wir formen

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

um zu

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

und kürzen durch 2

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

Da bereits $4n^{2}\leq 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*(n+1)^{2}\leq 4n^{2}$

Wieder durch 2 kürzen und ausquadrieren

$n^{2}+2n+1\leq 2n^{2}$

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

$0\leq n^{2}-2n-1$

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

$2\leq n^{2}-2n+1$

und zusammenfassen:

$2\leq (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}\leq 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}\leq 2^{n+1}$. Daher muss also auch gelten:

$4n^{2}+8n+4\leq 2^{n}+8n+4$

Soweit so gut. Nun müssen wir irgendwie zeigen, dass $2^{n}+8n+4\leq 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\leq 2^{n+1}$ ein erhält man:

$2^{8}+8*8+4=324\leq 2^{9}=512$

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

Unsere Induktionsbehauptung lautet: $2^{n+1}+8(n+1)+4\leq 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*2^{n}+8n+12$

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

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

Formen wir diese um, erhalten wir:

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

Dies lässt sich wieder einsetzen:

$2*2^{n}+8n+12\leq 2*(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\leq 2^{n+2}$

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

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

Was zu zeigen war.

--Ryus (Diskussion) 15:35, 11. Sep. 2015 (CEST)