TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 21

Aus VoWi
Zur Navigation springen Zur Suche springen

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

(n+1)3^n\le4^n

(ist auch Induktionsvoraussetzung, d.h. wir gehen davon aus, dass dies eine wahre Aussage ist)

Durch herumprobieren kommt man darauf, dass diese Ungleichung ab 8 gilt. Falls jemand weiß, wie man sie löst, kann er bitte die Lösung reinschreiben.

1.für welche n>=0 gilt die Ungleichung[Bearbeiten]

Einsetzten der Zahlen und schauen ob und ab wann die Aussage wahr ist:

  • n=0:  (0+1)*3^{0} \le 4^{0} , 1\le1  \Rightarrow Wahre Aussage
  • n=1:  (1+1)*3^{1} \le 4^{1} , 2*3\le4 , 6\le4  \Rightarrow Falsche Aussage
  • n=2:  (2+1)*3^{2} \le 4^{2} , 3^{3}\le16 , 27\le16  \Rightarrow Falsche Aussage
  • n=5:  (5+1)*3^{5} \le 4^{5} , 6*243\le1024 , 1358\le1024  \Rightarrow Falsche Aussage
  • n=7:  (7+1)*3^{7} \le 4^{7} , 8*2187\le16184 , 27\le16  \Rightarrow Falsche Aussage
  • n=8:  (8+1)*3^{8} \le 4^{8} , 9*6551\le 64776  , 58959\le64776  \Rightarrow Wahre Aussage

Ab 8 ist die Aussage wahr, wird auch für alle folgendne Zahlen so bleiben, da 4^{n} schneller wächst als 3^{n} \Rightarrow ab 8 gilt die Ungleichung

2. der Beweis mit vollständiger Induktion[Bearbeiten]

Durch das Induktionsprinzip erhalten wir die Ungleichung:
(n+2).3^{n+1} \le 4^{n+1}

(n+2).3^{n+1} \le 4^n*4

\frac{(n+2).3^{n+1}}{4} \le 4^n

Durch diverse Umformungen erhalten wir obige Ungleichung, wo wir auf der rechten Seite wieder eine Ausdruck haben (4^n), der in der ursprünglichen wahren Aussage vorhanden ist, dass Prinzip der vollständigen Induktion wäre jetzt, die ursprüngliche Aussage einfließen lassen, bis wir wieder auf eine wahre Aussage kommen.

\frac{(n+2).3.3^{n}}{4} \le 4^n

\frac{3}{4}.(n+2).3^{n} \le 4^n

Weiters wissen wir die Induktionsvorraussetzung: (n+1).3^n\le4^n

Daraus folgt die Abschätzung: \frac{3}{4}.(n+2).3^{n} \le (n+1).3^n \le  4^n

\frac{3}{4}.(n+2).3^{n} \le (n+1).3^n

\frac{3}{4}.(n+2) \le n+1

\frac{3}{4}.n+ \frac{3}{2} \le n+1

0 \le \frac{1}{4}.n - \frac{1}{2}

Also gilt die Behauptung für Alle n größer gleich 2! Da die Vorraussetzung erst ab n=8 gilt, stimmt die Aussage für alle n>=8

Hoffe die Weiterführung ist korrekt MfG Martin

Vorschlag zum Rausfinden des Induktionsanfangs:

Man kann die linke und die rechte Seite der Ungleichung als zwei Funktionen darstellen.
Dort wo sich die beiden Funktionen schneiden ergibt sich der Induktionsanfang.

- wie gesagt ist nur ein Vorschlag - MFG Morten