TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 45

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

$4n^2\le 2^n$

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=84$	$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=84$	$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/w/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)