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

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

$3n+2^{n}\leq 3^{n}$

Lösungsvorschlag

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

${\begin{aligned}n=0,\quad &3*0+2^{0}=&1\leq 3^{0}(1)&\quad richtig\\n=1,\quad &3*1+2^{1}=&5\leq 3^{1}(3)&\quad falsch\\n=2,\quad &3*2+2^{2}=&10\leq 3^{2}(9)&\quad falsch\\n=3,\quad &3*3+2^{3}=&17\leq 3^{3}(27)&\quad richtig\\n=4,\quad &3*4+2^{4}=&28\leq 3^{4}(81)&\quad richtig\\n=5,\quad &3*5+2^{5}=&47\leq 3^{5}(243)&\quad richtig\end{aligned}}$

Dies ergibt die Vermutung, daß die Gleichung für alle $n\geq 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\geq 3$ gilt.

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

Induktionsschluß:

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

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

Lösungsvorschlag

${\begin{alignedat}{2}3(n+1)+2^{n+1}&\leq 3^{n+1}\\3n+3+2\cdot 2^{n}&\leq 3\cdot 3^{n}\\3n+2^{n}+3+2^{n}&\leq 3\cdot 3^{n}\\3n+2^{n}&\leq 3\cdot 3^{n}-3-2^{n}\\3^{n}&\leq 3\cdot 3^{n}-3-2^{n}&&{\text{(*)}}\\3^{n}+3+2^{n}&\leq 3\cdot 3^{n}\\3+2^{n}+3^{n}&\leq 3^{n}+3^{n}+3^{n}\end{alignedat}}$

(*) $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!