Ungleichung durch vollständige Induktion beweisen

Question

Aufgabe:

Ich soll durch vollständige Induktion für n ≥ 4 beweisen, dass:

2ⁿ < n! < 2^{(n) hoch 2}

Problem/Ansatz:

Induktionsanfang kann ich mit n = 4 leicht beweisen:

16 < 24 < 65536 w.A

Induktionsvoraussetzung lautet also:

Ǝ n ∈ N: 2ⁿ < n! < 2^{(n) hoch 2}  

Induktionsschritt fällt mir da bisschen schwieriger:

Wie genau soll ich beweisen, dass das ganze auch für n +1 gilt?

Umgeformt würde meine Ungleichung so ausschauen:

2ⁿ * 2 < (n+1)! < 2^{(n+1) hoch zwei}

Wie gehe ich da dann weiter vor?

Answer 1

Du hast hier im Prinzip zwei Ungleichungen. Mache es also getrennt und wende jeweils die Induktionsvoraussetzung an.

Beispielsweise ist

\(2^{n+1}=2^n\cdot 2 \stackrel{2^n<n!}{<} n!\cdot 2 < n!(n+1)=(n+1)!\).

Die andere Ungleichung schaffst du vielleicht selbst.

Comments

Also den ersten Bruch kann ich beweisen. Da müsste ja gelten

2ⁿ⁺¹ < (n+1) * n! ist äquivalent zu 2ⁿ * 2 < (n+1) * n!

IV: 2n * 2 < n! * 2

n! * 2 ist aber auch kleiner als (n+1) * n!, da n größer gleich 4 ist.

Somit ist

2n+1 < (n+1) * n! bewiesen.

Mein Problem ist aber die andere Seite jetzt,

(n+1) * n! < 2^{(n+1) * (n+1)}

IV: n! * (n+1) < 2^{n * n} * (n+1)

Wie komm ich da jetzt weiter?

---

Aus dem Muster oben siehst Du, dass Du bei Ungleichungen mit Äquivalenzumformungen nicht weiterkommst. Man fängt mit einer Seite an und rechnet los, unter Verwendung der Ind.Ann., und muss dann sehen, dass man auf der anderen Seite rauskommt, s.o.

---

Zur ersten Ungleichung. Schau mal in meine Antwort. Schreib es direkt in einer logischen Reihenfolge auf, dann braucht man da nicht so "rumhampeln" und der Beweis ist auch sofort nachvollziehbar. Das gleiche gilt dann auch für die andere Ungleichung:
\((n+1)!=(n+1)n!<(n+1)2^{n^2}< \ldots< 2^{(n+1)^2}\)

Überlege dir, wie du die Lücke schließen kannst. Was fehlt dir, damit du auf die rechte Seite kommst?

---

ich habe keine ahnung. Ich denk mir, wie kann ich von n hoch 2 auf n+1 hoch zwei kommen? aber das geht halt nicht

---

Oder kann man da etwas weglassen? Weil weil n *n ist sicher kleiner als (n+1) * (n+1). Aber keine ahnung wie ich das mathematisch schön aufschreibe

---

aber das (n+1) macht mir da Probleme

---

Potenzgesetze kennst du doch sicher. Und \((n+1)^2=n^2+2n+1\)  ist dir sicherlich auch bekannt.

aber das (n+1) macht mir da Probleme

Dann versuch es doch abzuschätzen.

---

Und was kann ich dann damit anfangen? Ich hätte dann (n²  + 2n + 1) * 2^n*n und ich soll beweisen dass das kleiner ist als 2^{(n+1) hoch 2} . Ich komm da trotzdem auf nix

---

Und was kann ich dann damit anfangen? Ich hätte dann (n^2  + 2n + 1) * 2^(n*n)

Hier hast du etwas völlig missverstanden.

Dich stört das \((n+1)\), dann schätze es durch einen Term ab, mit dem du etwas anfangen kannst.

Du möchtest von \(2^{n^2}\) zu \(2^{(n+1)^2}\). Was fehlt dir dafür? Nutze Potenzgesetze und die binomische Formel. Wie kannst du das mit dem vorherigen Punkt in Verbindung bringen?

Darf man fragen, was du studierst?

---

mathematik auf lehramt

---

kannst du mir bitte zeigen, wie man das löst? ich habe keine Ahnung wie ich beweisen soll, dass (n^2  + 2n + 1) * 2^(n*n) kleiner ist als 2^{(n+1) hoch 2}  auch wenn ich mir den Faktor n^2... als l zusammenfasse hilft mir das nicht weiter. Und mit Potenzgesetzen kann ich nicht von n * n auf (n+1) * (n+1) kommen.

---

(n^2  + 2n + 1) * 2^(n*n)

Das ist doch gar nicht die Ausgangssituation, sondern \((n+1)2^{n^2}\).

Nutze \((n+1)\leq 2^n\) für \(n\geq 1\).

Wie nun schon mehrfach gesagt, sollst du den Faktor \((n+1)\), der dich so sehr stört, abschätzen.

Und mit Potenzgesetzen kann ich nicht von n * n auf (n+1) * (n+1) kommen.

Du willst ja auch von \(2^{n^2}\) auf \(2^{(n+1)^2}\) kommen.

---

2^{n hoch 2} * (n+1) < 2^{n hoch 2} + 2²ⁿ + 2

Soll ich da dann für das kleinste n schauen, ob es richtif ist? was meinst du mit abschätzen?

---

Abschätzen heißt, einen Ausdruck kleiner oder größer machen. Das ist doch das Ziel. Zum Beispiel ist \(n+5<n+10\) eine Abschätzung.

Das, was du da geschrieben hast, passt aber vorne und hinten nicht. Warum wird aus einem Produkt (linke Seite) plötzlich eine Summe (rechte Seite)?

Soll ich da dann für das kleinste n schauen, ob es richtif ist?

Nein, das ist nicht notwendig, wenn man zeigt, dass eine Abschätzung für alle \(n\), die man betrachtet, gilt.

---

man kann keine Abschätzung in dem Fall machen? Wie??? und ich hab meine Schritte weiter oben schon erklärt. Ich habe keine Lust auf eine Frage, eine Frage als Antwort zu kriegen, was schon seit stunden so geht. Ich lasse einfach das Beispiel....

---

man kann keine Abschätzung in dem Fall machen? Wie???

Das habe ich nie gesagt. Aber es ist völlig unklar, warum aus einem Produkt plötzlich eine Summe gilt.

Ich habe keine Lust auf eine Frage, eine Frage als Antwort zu kriegen, was schon seit stunden so geht. Ich lasse einfach das Beispiel....

Ich wollte mit dir den Lösungsweg erarbeiten, aber dir fehlt offenbar grundlegendes mathematisches Verständnis. Das meine ich nicht böse, aber ich sehe das ein wenig kritisch, wie man damit irgendwann einmal Schülern Mathematik beibringen möchte...

\(\red{(n+1)}\cdot 2^{n^2}< \red{2^n}\cdot 2^{n^2}\), weil \(n+1<2^n\) (das nennt sich Abschätzung). Jetzt musst du dir nur noch überlegen, warum

\(2^n\cdot 2^{n^2}< 2^{(n+1)^2}\) gilt (Potenzgesetze und eine weitere Abschätzung).

Vorsagen von Lösungen bringt übrigens so gut wie gar nichts, weil du dadurch kein Gefühl für solche Dinge entwickeln kannst. Einen Rechen- oder Lösungsweg nachzuvollziehen ist immer einfacher als ihn selbst zu entwickeln. Letzteres muss man aber unbedingt lernen und das geht nur durchs eigenständige Rechnen.

---

@A: Hältst Du die Abschätzung n+1<2^n für selbstverständlich?

---

Nein, aber für offensichtlich. Einen linearen Ausdruck durch einen exponentiellen Ausdruck abzuschätzen, darauf kann man kommen. Auch als Studienanfänger, wenn man ein gewisses Maß an mathematischem Verständnis hat, was man doch erwarten können sollte, wenn sich jemand bewusst für ein Studium der Mathematik, wenn auch nur auf Lehramt, entscheidet.

Zudem hatte ich ja dann auch den Tipp mit der Abschätzung gegeben, was dennoch nicht umgesetzt werden konnte.

---

Der Begriff "Abschätzung" ist vielen Anfängern nicht geläufig. Mit etwas basteln und schauen, was noch fehlt, kann man auf die Abschätzung kommen und sich dann überlegen, ob die gilt. Dieses Vorgehen ist aber auch erstmal nicht geläufig (das Vorgehen zu benennen hilft dann auch nicht). Hier fehlt eben (hoffentlich: noch) die Übung und Vertrautheit mit den Begriffen.

Wie auch immer, apfelmännchen hat die Abschätzung ja dann genannt ("nutze..."), danach sollte es auch bei Anfängern durchgehen. Hat hier aber auch nicht geholfen.