2^n>=n^2? Induktion?
Hey ihr Lieben,
ich fange demnächst ein Studium in Elektrotechnik an und möchte mich bestmöglich darauf vorbereiten. Im Vorfeld habe ich mich schon ein wenig mit dem Stoff beschäftigt und festgestellt, dass mich auch viele mathematische Beweise erwarten werden.
Leider bin ich in Mathe nicht besonders gut – trotzdem möchte ich mich der Herausforderung stellen und mein Bestes geben.
Aktuell beschäftige ich mich mit dem Beweis durch vollständige Induktion und bin dabei auf eine Aufgabe gestoßen, die mir große Schwierigkeiten bereitet. Beim Induktionsschritt komme ich nicht weiter.
Mir ist klar, dass exponentielle Funktionen deutlich schneller wachsen als quadratische, sodass der Zusatzterm 2n + 1 im Vergleich zu 2 \cdot 2^n keinen großen Unterschied mehr macht. Aber wie genau kann ich diesen Gedanken in den Beweis einbauen?
Liebe Grüße ☺️
Vielleicht kann man ja weiter, indem man von der Induktionsvoraussetzung eine mal 2 Dran multipliziert und von da aus zeigt, dass 2^n scheneller steigt als n^2 und mit einbringt das der Rest 2n+1 kaum etwas am Wachstum ausmacht.
4 Antworten
Also machen wir das erst ab n = 4:
Was nun zu beweisen wäre, ist
Das liest sich schon deutlich einfacher. Auch hier geht wieder Induktion. Beweis für n = 4, aber dort wollen wir ja beweisen
Und das ist noch kürzer, was zu beweisen gilt. Man sieht es natürlich für n > 4 recht schnell, aber auch hier eine Induktion (etwas überflüssig, aber weil es so schön ist):
Die erste Ungleich ist sofort ersichtlich (kann man ausmultiplizieren, ergibt 2n + 1 > 0), die zweite ergibt sich aus dem Induktionsanfang.
Vielleicht werfe ich ein falschen Blick auf dieses Problem. Ich sehr leider nicht woher das kommt.
also von 2* 2^n > n^2+2n+1 auf
—> n^2 > 2n+1 ?
Ah ok ups. Okay ich habe es jetzt selber gesehen 🫣😂
Du könntest wiefolgt fortfahren: wobei die Äquivalenz nach Induktionsvorraussetzuung gilt, da du ja n^2 bereits durch 2^n nach oben abschätzen kannst. Nun kannst du (durch Induktion) die letzte Ungleichung zeigen
IA. für n=3 gilt : 2^n>= 2n+1
2^3> 2*3+1 <=> 8>7
IV: Es existiert ein n aus den natürlichen Zahlen für die gilt: 2^n>=2n+1
IS.
n-> n+1
2^n+1>= 2*(n+1)+1 <=>. 2^n + 2*n >= 2n+2+1
2^n + 2^n >=( 2n+1) +1
1) 2^n >= 2n+1 (wie oben)
2) 2^n>= 1 für n=0
ist das so richtig? Ich habe selbst nur 2 Punkte im Abi gehabt, also wirklich ziemlich schlecht. Ich muss echt vieles aufholen.
Und vielen Dank für deine Hilfe☺️
Das ist beinahe richtig. Theoretisch brauchst du als Induktionsanfang nur n=4, da du bereits den Fall n=3 bei der anderen Ungleichung gezeigt hast. Der einzige Fehler ist, dass du aus der +2 eine +1 gemacht hast. Jedoch gilt offensichtlich für n>=1 die Unghleichung 2^n > 2.
Hinweis: Vor.: 2^n >= n^2 ; Beh. wahr für n=4 und n = 5 ; Beh. falsch für n =3 ;
2^(n+1) = 2 * 2^n = 2^n + 2^n >= (n+1)^2 = n^2 + 2n +1 ; <=> 2^n >= 2n +1 ; für n>3
Vielen Dank 😊 Also würde es als ausreichend gelten zu zeigen, dass die Ungleichung 2^n >= 2n + 1 für n > 3 erfüllt ist? Wäre ein zweiter Durchlauf des Induktionsbeweises dann nicht mehr notwendig?
Beweis per vollständiger Induktion (für n≥4):
Induktionsanfang (n=4):
2⁴ = 16 ≥ 4² = 16. ✓
Induktionsschritt:
Angenommen, für ein k≥4 gilt 2ᵏ ≥ k², dann 2ᵏ⁺¹ = 2·2ᵏ ≥ 2·k²
Wir müssen zeigen:
2·k² ≥ (k+1)² = k²+2k+1⟺ k² – 2k – 1 ≥ 0.
Für k≥4 ist k² – 2k – 1 = (k–1)² – 2 ≥ 2² – 2 = 2 ≥ 0. ✓
Damit folgt, dass 2ⁿ ≥ n² für alle n>3 gilt.
Ich verstehe nicht so wirklich, wieso man jetzt : 2n^2> 2n+1 beweisen soll und woher 2n^2 kommt.