TU Wien:Mathematik 1 UE (diverse)/Übungen SS10/Beispiel 3

Man untersuche durch vollständige Induktion, für welche $n\ge 0$ folgende Ungleichung gilt:

$3n+2^n\le 3^n$

Lösungsvorschlag

Als ersten Schritt untersuchen wir die Gleichung durch Einsetzen für n:

$\begin{array}{cccc}n=0,& 3\ast 0+2^0=& 1\le 3^0(1)& richtig\\ n=1,& 3\ast 1+2^1=& 5\le 3^1(3)& falsch\\ n=2,& 3\ast 2+2^2=& 10\le 3^2(9)& falsch\\ n=3,& 3\ast 3+2^3=& 17\le 3^3(27)& richtig\\ n=4,& 3\ast 4+2^4=& 28\le 3^4(81)& richtig\\ n=5,& 3\ast 5+2^5=& 47\le 3^5(243)& richtig\end{array}$

Dies ergibt die Vermutung, daß die Gleichung für alle $n\ge 3$ gilt, da $3^n$ stärker wächst als $2^n$.

Der Induktionsanfang für n = 3 ist bereits bewiesen.

Die Induktionsvoraussetzung, daß die Gleichung für alle $n\ge 3$ gilt.

Die Induktionsbehauptung: $3(n+1)+2^{n+1}\le 3^{n+1}$

Induktionsschluß:

 $3\ast (n+1)+2^{n+1}\le 3\ast (3n+2^n)\le 3^{n+1}=3\ast 3^n$  | Term * 3
   $3n+3+2\ast 2^n\le 9\ast n+3\ast 2^n$	               |$-2\ast 2^n,-3\ast n$
                  $3\le 6\ast n+2^n$

und die Gleichung ist für alle $n\ge 3$ und $n=0$ bewiesen.

Lösungsvorschlag

$\begin{array}{cc}3(n+1)+2^{n+1}& \le 3^{n+1}\\ 3n+3+2\cdot 2^n& \le 3\cdot 3^n\\ 3n+2^n+3+2^n& \le 3\cdot 3^n\\ 3n+2^n& \le 3\cdot 3^n-3-2^n\\ 3^n& \le 3\cdot 3^n-3-2^n& & \text{(*)}\\ 3^n+3+2^n& \le 3\cdot 3^n\\ 3+2^n+3^n& \le 3^n+3^n+3^n\end{array}$

(*) $3^n$ ist sicher größer oder gleich $3n+2^n$

Anmerkung:

$3^n$ ist sicher größer oder gleich $3n+2^n$ bezieht sich aus der Angabe!