TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS13/Beispiel 81

Aus VoWi
Zur Navigation springen Zur Suche springen

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

4n^2 \leq 2^n


Lösung[Bearbeiten]

Induktionsanfang : Der Induktionsanfang muss gefunden werden.

n=0: \quad 0 \leq 1 \qquad \mathrm{w.A.}

n=1: \quad 4 \leq 2 \qquad \mathrm{f.A.}

n=2: \quad 16 \leq 4 \qquad \mathrm{f.A.}

n=3: \quad 36 \leq 8 \qquad \mathrm{f.A.}

n=4: \quad 64 \leq 16 \qquad \mathrm{f.A.}

n=5: \quad 100 \leq 32 \qquad \mathrm{f.A.}

n=6: \quad 144 \leq 64 \qquad \mathrm{f.A.}

n=7: \quad 196 \leq 128 \qquad \mathrm{f.A.}

n=8: \quad 256 \leq 256 \qquad \mathrm{w.A.}

n=9: \quad 324 \leq 512 \qquad \mathrm{w.A.}

Man könnte nun vermuten, dass die Ungleichung für n \geq 8 gültig ist.


Induktionsvoraussetzung :

Aus den obigen Berechnungen ergibt sich die Induktionsvoraussetzung.

n: \quad 4n^2 \leq 2^n, \quad (n \geq 8)


Induktionsbehauptung:

Wir behaupten nun, dass die Ungleichung auch für n+1 gilt.

n+1: \quad 4(n+1)^2 \leq 2^{n+1}


Induktionsschritt:

Zu zeigen ist, dass n \to n+1.

n \to n+1: \quad 4(n+1)^2 \leq 2^{n+1}

Die Potenz der rechten Seite kann umgeformt werden.

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

Beide Seiten durch 2 dividieren.

2(n+1)^2 \leq 2^{n} \qquad | :2

An dieser Stelle kommt man mit dieser Form nicht recht weiter. Aber man kann sich die Induktionsvoraussetzung 4n^2 \leq 2^n zu Hilfe nehmen und auf der rechten Seite einsetzen. Damit ergibt sich die neue Ungleichung 2(n+1)^2 \leq 4n^2 \leq 2^n. Wenn nun diese stärkere Bedingung gültig ist, dann folgt daraus, dass die ursprüngliche Ungleichung auf jeden Fall erfüllt ist. Anders ausgedrückt: 2(n+1)^2 \leq 4n^2 \to 2(n+1)^2 \leq 2^{n}

2(n+1)^2 \leq 4n^2

Man kann wieder beide Seiten durch 2 dividieren.

(n+1)^2 \leq 2n^2 \qquad | :2

Und die linke Seite ausquadrieren.

n^2 + 2n + 1 \leq 2n^2

Und die linke Seite auf beiden Seiten subtrahieren.

0 \leq n^2 -2n -1 \qquad | -n^2 -2n -1

2 auf beiden Seiten addieren.

2 \leq n^2 -2n + 1 \qquad | +2

Die rechte Seite kann nun zusammengefasst werden.

2 \leq (n-1)^2

Man kann nun sehr einfach sehen, dass diese Ungleichung für n \geq 3 immer erfüllt ist und weil 2(n+1)^2 \leq 4n^2 \to 2(n+1)^2 \leq 2^{n} gilt, ist auch die ursprüngliche Ungleichung wahr. Wir haben gezeigt, dass 4n^2 \leq 2^n, \quad (n \geq 8) gültig ist. \Box