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

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

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

Lösung

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$