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

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

$4n^2\le 2^n$

Lösung

Induktionsanfang : Der Induktionsanfang muss gefunden werden.

$n=0:0\le 1\mathrm{w}\mathrm{.}\mathrm{A}\mathrm{.}$

$n=1:4\le 2\mathrm{f}\mathrm{.}\mathrm{A}\mathrm{.}$

$n=2:16\le 4\mathrm{f}\mathrm{.}\mathrm{A}\mathrm{.}$

$n=3:36\le 8\mathrm{f}\mathrm{.}\mathrm{A}\mathrm{.}$

$n=4:64\le 16\mathrm{f}\mathrm{.}\mathrm{A}\mathrm{.}$

$n=5:100\le 32\mathrm{f}\mathrm{.}\mathrm{A}\mathrm{.}$

$n=6:144\le 64\mathrm{f}\mathrm{.}\mathrm{A}\mathrm{.}$

$n=7:196\le 128\mathrm{f}\mathrm{.}\mathrm{A}\mathrm{.}$

$n=8:256\le 256\mathrm{w}\mathrm{.}\mathrm{A}\mathrm{.}$

$n=9:324\le 512\mathrm{w}\mathrm{.}\mathrm{A}\mathrm{.}$

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

Induktionsvoraussetzung :

Aus den obigen Berechnungen ergibt sich die Induktionsvoraussetzung.

$n:4n^2\le 2^n,(n\ge 8)$

Induktionsbehauptung:

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

$n+1:4(n+1{)}^2\le 2^{n+1}$

Induktionsschritt:

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

$n\to n+1:4(n+1{)}^2\le 2^{n+1}$

Die Potenz der rechten Seite kann umgeformt werden.

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

Beide Seiten durch $2$ dividieren.

$2(n+1{)}^2\le 2^n|:2$

An dieser Stelle kommt man mit dieser Form nicht recht weiter. Aber man kann sich die Induktionsvoraussetzung $4n^2\le 2^n$ zu Hilfe nehmen und auf der rechten Seite einsetzen. Damit ergibt sich die neue Ungleichung $2(n+1{)}^2\le 4n^2\le 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\le 4n^2\to 2(n+1{)}^2\le 2^n$

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

Man kann wieder beide Seiten durch $2$ dividieren.

$(n+1{)}^2\le 2n^2|:2$

Und die linke Seite ausquadrieren.

$n^2+2n+1\le 2n^2$

Und die linke Seite auf beiden Seiten subtrahieren.

$0\le n^2-2n-1|-n^2-2n-1$

$2$ auf beiden Seiten addieren.

$2\le n^2-2n+1|+2$

Die rechte Seite kann nun zusammengefasst werden.

$2\le (n-1{)}^2$

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