erklärungen zur vollständige Induktion für 2^n > n²

Neue Frage »

priscylla Auf diesen Beitrag antworten »
erklärungen zur vollständige Induktion für 2^n > n²
Hallo zusammen,
ich habe gerade mein Studium begonnen und war ausgrechnet die 2te also vorige Woche krank...
Nun versuche ich das verpasste nachzuholen und sitze an der vollst. Induktion von Ungleichungen.
ich habe mir schon einiges durchgelesen und videos angeschaut aber irgendwie komme ich nicht weiter. Ich habe zwar die Lösung (durchs Netz) aber ich kann sie nicht nachvollziehen.

Die Aufgabe lautet:
2^n > n² für n>=5

ICh fange also mit dem Induktionsanfang an: n=5
2^5 > 5²
32 > 25, stimmt also

Weiter mit dem IS
Voraussetzung: n=k
2^k > k²

Behauptung: n=k+1


jetzt les ich hier:

ok, das leuchtet mir ein

weiter steht da:

hab ich ne Weile gebraucht aber versteh ich jetzt auch. Wenn gilt 2^k > k² gilt das auch wenn ich auf beiden seiten das selbe multipliziere.
So weit so gut.

nun übernehm ich aber plötzlich diese 2k² und das versteh ich nicht
wenn k² kleiner ist als 2^k wieso kann ich dann davon ausgehen das es trotzdem GRÖßER ist als (k+1)²

das wäre also meine erste Frage.

Dann übernehm ich das mal so, und habe:
2k² > (k+1)²
Binom auflösen und das ganze rüber nehmen, ist klar, dann habe ich
k²-2k > 1
jetzt steht aber im nächsten Schritt plötzlich:
k²-2k+1>2
wieso wurde jetzt einfach eine 1 addiert? also ich nehme an für den nächsten Schritt aber wie kommt man denn auf so was?
dann folgt ja
(k-1)² >2
und das war es dann? Aber warum? Was ist denn dadurch bewiesen?

also das ist mir wirklich nicht ganz klar und umso mehr ich nachlese um so verwirrter werde ich.
Ich hoffe ihr könnt den Knoten in meinem Kopf auflösen. smile
Gast11022013 Auf diesen Beitrag antworten »
RE: erklärungen zur vollständige Induktion für 2^n > n²
Zitat:
ICh fange also mit dem Induktionsanfang an: n=5


Weißt du auch warum der Induktionsanfang n=5 sein sollte und nicht etwa n=1?
Für n=1 stimmt es ja auch.

Zitat:
weiter steht da:


Bei der vollständigen Induktion versucht man immer zu erreichen irgendwie die Induktionsvoraussetzung anzuwenden.
Das wäre hier, dass

für ein festes aber beliebiges natürliches n gilt.

Um die Induktionsvoraussetzung "wiederzufinden" vereinfachen wir den Ausdruck



Auf die 2^k können wir nun die Induktionsvoraussetzung anwenden. Von den 2^k wissen wir ja, dass sie größer sind als k^2 (für )

Ich finde den von dir präsentierten Lösungsweg ein wenig undursichtig. Das geht meiner Meinung nach leichter und verständlicher.

Versuch es so:

Wir sind gerade dabei abzuschätzen. Um die Induktion zu beenden müssen wir also nur noch irgendwie



zeigen.

Unser Ziel sollte es also sein irgendwie nach unten durch abzuschätzen.
Nun ist ja erstmal



Was jetzt noch zu tun wäre ist, dass zusätzliche nach unten gegen abzuschätzen.

Anstelle es also einfach hinzuschreiben und dann irgendwie zu lösen würde ich es immer vorziehen es als "Ungleichungskette" zu notieren und durch Abschätzungen zu der notwendigen Form zu gelangen. Also eher in der Art:




Zitat:
wieso wurde jetzt einfach eine 1 addiert? also ich nehme an für den nächsten Schritt aber wie kommt man denn auf so was?
dann folgt ja
(k-1)² >2
und das war es dann? Aber warum? Was ist denn dadurch bewiesen?


Die Idee war auch hier die zweite binomische Formel auf der linken Seite zu erzeugen. Dazu fehlte noch das +1.
Deshalb hat man es also einfach dazuaddiert. So kannte man dann



umformen.
Und dies gilt nun, unter der Voraussetzung, dass ist, für alle .

Denn (k-1)^2 wird minimal wenn k=5 ist. Aber selbst dann ist es locker größer als 2



Für größere k-Werte wird es natürlich immer noch größer als 2 sein.
Und mehr wollen wir ja gar nicht wissen.

ist sogesehen eine "abgeschwächte" Form der Ungleichung



Nur das bei

die Gültigkeit besser erkennen können.
priscylla Auf diesen Beitrag antworten »

Erstmal danke für deine schnelle, ausführliche Antwort!

Zitat:
Weißt du auch warum der Induktionsanfang n=5 sein sollte und nicht etwa n=1?
Für n=1 stimmt es ja auch.

Also da in der Aufgabe vorgegeben war es soll für n>=5 gelten und man, wenn ich das richtig verstanden habe, immer die kleinstmögliche Zahl für die die Behauptung stimmt nehmen soll.

Zitat:
Von den 2^k wissen wir ja, dass sie größer sind als k^2 (für )


genau da hab ich den knoten
ich weiß das 2^k>k² demzufolge ist auch 2*2^k > 2*k²
im umkehrschluß heißt das doch das 2*k KLEINER ist als 2*2^k
woher weiß ich dann das es trotzdem größer ist als (k+1)²

setze ich da immer die 5 in Gedanken ein und prüfe das?
also 2*2^5 > (5+1)²
64>36

Zitat:
Anstelle es also einfach hinzuschreiben und dann irgendwie zu lösen würde ich es immer vorziehen es als "Ungleichungskette" zu notieren und durch Abschätzungen zu der notwendigen Form zu gelangen. Also eher in der Art:



das versteh ich leider nicht. Weiß nicht wie die Kette dann hier aussehen soll.


Also formt man das ganze im Grunde nur so lange um bis man genauer sehen kann das die Ungleichung stimmt?
Bei der Induktion einer Summenformel hat man ja am Ende z.b. das auf beiden Seiten das gleiche steht und damit ist es bewiesen. Und hier ist es immer nur "abgeschätzt" oder?

Ich glaub ich sollte mich auch nochmal mit Ungleichungen beschäftigen..
Gast11022013 Auf diesen Beitrag antworten »

Zitat:
Also da in der Aufgabe vorgegeben war es soll für n>=5 gelten und man, wenn ich das richtig verstanden habe, immer die kleinstmögliche Zahl für die die Behauptung stimmt nehmen soll.


Wie gesagt, die Ungleichung würde ja auch schon für n=1 gelten.

2^1>1^2

Oder auch für n=0

2^0>0^2

Wieso ist es trotzdem sinnvoll den Induktionsanfang für n=5 festzumachen?

Zitat:
Also formt man das ganze im Grunde nur so lange um bis man genauer sehen kann das die Ungleichung stimmt?
Bei der Induktion einer Summenformel hat man ja am Ende z.b. das auf beiden Seiten das gleiche steht und damit ist es bewiesen. Und hier ist es immer nur "abgeschätzt" oder?


Wenn man einen Induktionsbeweis für eine Ungleichung führt, dann schätzt man meistens eher grob ab als Umformungen zu tätigen.

In der Rechnung, welche du vorstellt hast, wurden auch Umformungen gemacht um es letztendlich zu zeigen.
Das ist aber nicht notwendig.
Durch Abschätzungen kann man einen Ausdruck erst einmal "handlicher" machen.
Dabei muss man jedoch aufpassen, dass man nicht zu grob abschätzt.

Zitat:
ich weiß das 2^k>k² demzufolge ist auch 2*2^k > 2*k²
im umkehrschluß heißt das doch das 2*k KLEINER ist als 2*2^k
woher weiß ich dann das es trotzdem größer ist als (k+1)²


Du möchtest irgendwie zeigen, dass ist.

Soweit waren wir gekommen:



Hier musst du nun weitermachen und noch begründen weshalb ist, womit du deine Induktion beenden würdest.
priscylla Auf diesen Beitrag antworten »

Zitat:
Wieso ist es trotzdem sinnvoll den Induktionsanfang für n=5 festzumachen?


Weil es bei 3 nicht stimmt und bei 4= wäre?

Zitat:
Hier musst du nun weitermachen und noch begründen weshalb ist, womit du deine Induktion beenden würdest.


Wie meinst du das mit begründen?
prüfe ich dann ob es für 5 gilt und dass es dann erst recht für größere Zahlen gilt?
also aus der Zeile ergibt sich ja wieder
2k² >(k+1)²

uff.. ich sehe gerade nur noch k's

ich geh mal fix einkaufen und hol mir was zu essen. Vielleicht kann ich dann besser denken -.-*
Gast11022013 Auf diesen Beitrag antworten »

Zitat:
Weil es bei 3 nicht stimmt und bei 4= wäre?


Du meinst wahrscheinlich das richtige.
Natürlich gilt es auch schon für n-Werte die kleiner als 5 sind, aber nun mal auch für einige nicht.
Erst ab 5 gilt es wirklich für jedes natürliche n. Deshalb macht es Sinn den Induktionsanfang für n=5 festzusetzen.

Dabei musst du gegebenenfalls auf die Aufgabenstellung achten.
Sie könnte zum Beispiel auch so lauten, dass du alle natürlichen Zahlen angeben sollst für die die Ungleichung gilt. Dann würdest du einpaar vergessen, wenn du die n-Werte <5 nicht noch nennst.

Zitat:
Wie meinst du das mit begründen?


Damit meine ich natürlich, dass du deine Schritte begründen sollst.
Natürlich kannst du einfach

Zitat:
also aus der Zeile ergibt sich ja wieder
2k² >(k+1)²


hinschreiben. Dann finde ich es aber nicht begründet. Wie kommst du darauf?
 
 
priscylla Auf diesen Beitrag antworten »

ok, aber in dem fall kann ich das einfach so nehmen ja?

und wenn es nicht so wäre müsste ich dann probieren oder verbal begründen?

wobei wir wieder bei begründen sind, verbal oder wieder durch zwischenschritte?

also bei
wenn

ist auch

und da

ist


vielleicht hab ich auch das ganze induktionsprinzip noch nicht ganz verstanden...
Gast11022013 Auf diesen Beitrag antworten »

Naja, so wie du es aufschreibst mach es halt irgendwie den Anschein als wäre dir nicht ganz klar, dass nun eben



ist.

Irgendwie begründen solltest du das schon, das muss auch nicht viel sein und manche Abschätzungen sind auch "offensichtlich".
Mache es nicht schwerer als es ist.

Eine sprachliche Begründung für eine Ungleichung würde ich vielleicht nicht unbedingt vorziehen. Dann lieber eine Rechnung. Zum Beispiel könntest du, wenn du überhaupt keine Idee hast, gewisse Abschätzungen ebenfalls wieder mit Induktion zeigen.

Also eine Induktion in einer Induktion. Das ist aber nicht sonderlich schön.

Aufschreiben ließe es sich zum Beispiel so:



So würde es meiner Meinung nach schon ausreichen.
Das für ist, das musst du nicht noch durch eine Rechnung begründen. Das das für gilt, ist klar.
Du könntest zum Beispiel auch hier schreiben
Denn k ist ja minimal 5. Es wird also einfach ein k durch 5 ersetzt.

In die letzte Ungleichung geht wieder ein, dass ist. Dann ist das natürlich größer als wie wenn du k durch 1 ersetzt.
priscylla Auf diesen Beitrag antworten »

Puh,
ok, die Zeile erschlägt mich gerade XD
Ich versuche mal die ganzen Infos zusammenzupacken und eine vollständige Induktion nochmal aufzuschreiben...
Aber jetzt brauch ich glaub ich ne pause. Totale Blockade...

Danke für deine Hilfe. Vielleicht hast du ja morgen nochmal Zeit? smile

Ach so, aber was bedeuten denn jetzt die I.V. ?
Gast11022013 Auf diesen Beitrag antworten »

I. V. steht für Induktionsvoraussetzung. Das ist ja das was du mit dem Induktionsanfang zeigst.

Für beliebiges, aber festes mit ist

Edit:

Gehe die Zeile einfach mal Schritt für Schritt durch.
Da passiert nichts großartiges, du musst dir nur die Relationszeichen klar machen.
Der kurze Kommentar darüber sollte dir dabei helfen.
priscylla Auf diesen Beitrag antworten »

Ok, du hast recht. Die Zeile ist eigentlich gar nicht so schwer.
Aber ich würde da wahrscheinlich nie so drauf kommen.

Ich versuch es jetzt nochmal anders aufzuschreiben.

Im Grunde dreht man sich doch im Kreis und beweist dadurch das es stimmt oder?
priscylla Auf diesen Beitrag antworten »

Ok, mit der Zeile von dir bekomme ich es nicht - für mich - nachvollziehbar aufgeschrieben.

Ich habe es jetzt so. Nicht so elegant aber hoffe vollständig?
Gast11022013 Auf diesen Beitrag antworten »

Das sollte richtig sein, auch wenn ich deine Art wie du den Induktionsschritt notierst irgendwie eigenartig finde.

Warum benennst du zum Beispiel n=k um?
priscylla Auf diesen Beitrag antworten »

Ehm,
also wie gesagt war ich jetzt ne Woche krank und habe das nachgeholt
und in den Aufzeichnungen die ich bekommen habe mit der beispiel Induktion da hat der Dozent das auch so gemacht.
smile
ICh wollte es einfach anpassen, an das wie der Professor es vorgibt.
Gast11022013 Auf diesen Beitrag antworten »

Das ist ja auch nichts schlimmes, ich fand die Notation nur ein wenig ungewohnt.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »