TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 20

Man untersuche durch vollständige Induktion, für welche n >= 0 folgende Ungleichung gilt:

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

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

SS08 Beispiel 3

Lösungsvorschlag

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

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

Dies ergibt die Vermutung, dass 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, dass 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. //Heholord fragt: Warum ist sie damit für $n\geq 3$ und $n=0$ bewiesen? A: wenns für 3 gilt und für den nachfolger von 3 (3+1) gilt, dann hast dus für alle ab 3 bewiesen. und 0 einsetzen

Hapi

Lösungsvorschlag von Ryus

Induktionsanfang siehe oben.

Zum Induktionsschritt:

Unsere Induktionsvoraussetzung lautet: $3n+2^{n}\leq 3^{n}$

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

Die beste Vorgehensweise bei Ungleichungen ist, nicht beide Seiten gleichzeitig umzuformen, sondern eine Kette aus = und $\leq$-Ketten zu bilden, um so von der linken Seite auf die rechte zu kommen (siehe [1]). Wir fangen also mit der linken Seite an und formen sie ein bisschen um:

$3(n+1)+2^{n+1}=3n+3+2*2^{n}$

Wir müssen es irgendwie schaffen, unsere Induktionsvoraussetzung zu nutzen. Um dies zu schaffen, formen wir unsere Induktionsvoraussetzung etwas um:

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

Diese umgeformte IVR können wir nun in unsere letzte Formel einsetzen und dann weiter umformen:

$3n+3+2*2^{n}\leq 3n+3+2*(3^{n}-3n)=3n+3+2*3^{n}-2*3n=2*3^{n}+3-3n$

Was steht hier nun? Wir haben $2*3^{n}$, dazu wird 3 dazu addiert und 3n subtrahiert. 3n ist sicher größer als 3 (da $n\geq 3$ laut Induktionsanfang). Daher ist $3-3n$ sicher kleiner 0. Sprich wir ziehen etwas von $2*3^{n}$ ab. Lassen wir diese Subtraktion einfach weg, erhalten wir etwas, was sicher größer ist.

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

Nun folgen ein paar simple Schritte:

$2*3^{n}\leq 3*3^{n}=3^{n+1}$

Wir haben nun also eine lange Kette gebildet, auf deren linker Seite $3(n+1)+2^{n+1}$ steht, dann folgen lauter = bzw $\leq$, und am rechten Ende steht $3^{n+1}$. So haben wir also die Induktionsbehauptung gezeigt und die Aussage bewiesen.

--Ryus (Diskussion) 21:58, 18. Okt. 2015 (CEST)