2^n > n^2



  • Hallo,

    bei dem Beispiel nach dem Beweis, ob 2^n > n^2 ist, hänge ich völlig. Die Angabe "für n > n_0") verstehe ich leider gar nicht.
    Bitte keine Lösungen, aber einen Kick in die richtige Richtung!
    Und eventuell eine Literaturempfehlung ^^


  • Mod

    Nun, rechne doch mal die ersten fünf oder sechs n durch und guck mal, ob dir da etwas auffällt. Und dann denkst du mal darüber nach, ob die Tendenz die man da siehst wohl so weiter gehen wird und, wenn ja, warum. Dazu bietet es sich vielleicht an, den Fall eines n mit dem Fall seines Nachfolgers zu vergleichen *hint* *hint* 😃 .



  • Ich weiß, die Fragen sind eher doof gestellt, aber nach Jahren ohne Mathe will ich jetzt mal mit einem Informatikstudium anfangen, wo mal einfach vorausgesetzt ist, dass wir die vollständige Induktion beherrschen. Naja, ich bin eh ein Fan davon, autodidakt zu lernen, aber ohne auch das geringste Stück guidance ist das eben schwer...

    Die Überlegung ist also, dass 2^n > n^2 ist, und das 2^n * 2 > (n+1)^2 ist, das macht ausmultipliziert 2^n * 2 > n^2 + 2n + 1 - d.h. 2^n + 2^n > n^2 + 2n + 1 (ausgerechnet da bin ich hängen geblieben!), also 2^n muss > 2n + 1 sein, was erklärt, warum das erst ab Zahl 5 (2*1 + 1) gilt.
    Bloß, wie schreib ich's auf?

    Ach, noch zur Vorwarnung: Ich hoffe es geht klar, wenn ich in der nächsten Zeit mehr solche Anfängerfragen hier reinstelle...

    Danke schonmal im Voraus 🙂



  • sowie schrieb:

    d.h. 2^n + 2^n > n^2 + 2n + 1 (ausgerechnet da bin ich hängen geblieben!), also 2^n muss > 2n + 1 sein,

    Hast Du gerade 2^n = n^2 benutzt?



  • Es hilft, die Beispiele aus Buch und Internet nachzurechnen.


  • Mod

    Ach, erste Woche, erstes Semester Mathematik. Da habe ich mal Spaß und gebe dir ganz viele Tipps:
    Gucken wir mal für 2^n das Verhältnis von n zu n+1 an:
    2^(n+1) / 2^n = 2
    Also Verdoppelung, wenn man einen Schritt weiter geht.

    Nun das gleiche für n^2:
    (n+1)^2 / n^2 = (n^2 + 2n + 1) / n^2
    Schon komplizierter. aber es ist klar, dass solange 2n+1 < n^2 ist, dann ist das Ergebnis < 2. Man sieht leicht, dass dies für alle n>=3 erfüllt ist (Beweis durch dich. Gleiches Prinzip wie hier, aber noch einfacher). Wenn man also ein n>2 findet, bei dem 2^n > n^2 ist, dann gilt dies auch für alle nachfolgenden n, da 2^n schneller wächst.
    Durch Ausprobieren (ja, auch das ist eine legitime Vorgehensweise) findet man für n=4 die Werte 16 und 16 und für n=5 32 und 25. Folglich ist 2^n > n^2 für alle n>4.



  • SeppJ schrieb:

    Ach, erste Woche, erstes Semester Mathematik. Da habe ich mal Spaß und gebe dir ganz viele Tipps:
    Gucken wir mal für 2^n das Verhältnis von n zu n+1 an:
    2^(n+1) / 2^n = 2
    Also Verdoppelung, wenn man einen Schritt weiter geht.

    Nun das gleiche für n^2:
    (n+1)^2 / n^2 = (n^2 + 2n + 1) / n^2
    Schon komplizierter. aber es ist klar, dass solange 2n+1 < n^2 ist, dann ist das Ergebnis < 2. Man sieht leicht, dass dies für alle n>=3 erfüllt ist

    da 0 < n^2-2n-1 und daher 2 < (n-1)^2, also n > 2 und weil gilt n > n_0 ist n < -1 egal.
    soweit ist es mir klar, das mit der änderung vom einem aufs nächste hätte ich ja auch noch gecheckt. jetzt brauche ich noch ein n>2, für das gilt 2^n > n^2, und das ist n=5. und das war's?

    wenn ich das ganze aufschreiben müsste, müsste ich das also so tun?

    Zu zeigen: 2^n > n^2 für n > n_0
    2^(n+1) / 2^n = 2
    2n+1 < n^2 => (n+1)^2 / n^2 < 2
    n > 2 => (n+1)^2 / n^2 < 2
    
    2^n > n^2 ab n>2, da (n+1)^2 / n^2 < 2:
    2^3 = 8 > 9 = 3^2 - falsch
    2^4 = 16 > 16 = 4^2 - falsch
    2^5 = 32 > 25 = 5^2 - wahr
    
    2*2^n > 2*(n^2) > (n+1)^2 (wegen 2^n > n^2) = n^2 + 2n + 1
    d.h. n^2 + n^2 > n^2 + 2n + 1 und das gilt für n > 2
    

    oder fehlt da jetzt was?



  • Ich glaube, ich hatte einfach nur ein Problem damit, herauszufinden, was n_0 ist.

    Mit ein paar anderen Induktionen tu ich mir irgendwie leichter, glaube ich. Nur zum Abchecken daher:

    Zu zeigen

    $ (1+a\_1)(1+a\_2)\dots(1+a\_n) > 1 + a\_1 + a\_2 + \dots + a\_n $

    für

    ai(i=1,...,n)>0undn>1a_i (i = 1,...,n) > 0 und n > 1

    Anfang:

    $(1+a\_1)(1+a\_2) > 1 + a\_1 + a\_2 \Leftrightarrow 1+a\_1+a\_2+a\_1*a\_2 > 1 + a\_1 + a\_2 \Leftrightarrow a\_1 * a\_2 > 0, weil a_i > 0 $

    Schluss:

    $(1+a\_1)(1+a\_2)...(1+a\_n)(1+a\_(n+1)) > (1+a_(n+1) * (1 + a\_1 + a\_2 + ... + a\_n) = 1 + a\_1 + a\_2 + ... + a\_n + a_(n+1) + a\_1\*a\_(n+1) + a\_2\*a\_(n+1) + ... + a\_n*a\_(n+1) > 1 + a\_1 + a\_2 + ... + a\_n + a\_(n+1) $

    weil a_i > 0

    Wenn das so wenigstens stimmt, sehe ich zumindest noch Hoffnung ^^



  • Hallo,

    das ist leider Quark. Wo setzt du denn die Induktionsvoraussetzung ein?
    Die Erste Zeile des Induktionsschlusses müsste so aussehen
    IS: n-> n+1

    $(1+a\_1)(1+a\_2)...(1+a\_n)(1+a\_(n+1)) > 1 + a\_1 + a\_2 + ... + a\_n + a\_(n+1) $

    nach IV gilt...

    ps.: Ich finde das übrigens sinnvoll die Induktionsvoraussetzung auch hinzuschreiben.
    Und vielleicht solltest du dir das Induktionsprinzip generell nochmal (vielleicht an einer einfachen Aufgabe) klar machen.



  • Meine Überlegung war schon, wenn gilt
    $(1 + $a_1)(1 + $a_2)\dots(1 + a\_n) > 1 + a\_1 + a\_2 +\dots+a\_n$
    dann muss ich mittels Induktion zeigen, dass Links mit $$(1 + an+1)a_{n+1}) multipliziert immer noch größer ist als $$ + a_{n+1}$$ auf der rechten Seite. Aber das habe ich nicht aufgeschrieben, stimmt.

    Aber wenn ich auf der linken Seite mit 1 + a_{n+1} multipliziere, dann kann ich auf der rechten Seite auch damit multiplizieren, und weil das doch eine Äquivalenzumformung ist, gilt dann immer noch Links > Rechts.

    Dann dachte ich, dass wenn ich zeige, dass nach n=>n+1 die ursprüngliche Rechte seite kleiner ist, als die mit (1+a_{n+1}) multiplizierte (Äquivalenzumformung), dann doch klar sein müsste, dass die n+1.e rechte Seite auch kleiner als die n+1.e linke Sein muss.

    Oder nicht?



  • Ah, okay, dann war ich zu schnell mit meinem 'Quark'.
    Aber du hast es sehr schwer verständlich aufgeschrieben; ich würde es mir anders angewöhnen.
    Ist aber dann doch richtig.



  • Hmm, vielleicht hilft es dir bei Beweisen mit vollständiger Induktion diesen Schritten zu folgen (um den Beweis aufzuschreiben):

    1. Verankerung
    2. Annahme
    3. Zu Zeigen
    4. Beweis
      (Oder 1 und 2 vertauscht)

    Beispiel

    $2^n>n^2 for\ n>n_0$$$: Verankerung: $$$2^5>5^2$

    Annahme:

    $2^n>n^2$

    Zu zeigen:

    $2^{n+1}>(n+1)^2$

    Beweis

    \begin{eqnarray} 2^{n+1}&=&2*2^n\\ &>&2*n^2 \text{(Annahme)}\\ &=&n^2+n^2\\ &>&n^2+2n+1\\ &=&(n+1)^2 \end{eqnarray}

    So in etwa würde ich das aufschreiben. Bei (4) habe ich n^2>2n+1 verwendet, das hast du ja bei dir auch verwendet.


Log in to reply