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

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

$4n^{2}\leq 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*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}=84$	$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}=84$	$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!):