vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:43 Mo 22.10.2007 | | Autor: | jura |
| Aufgabe | Beweisen Sie durch vollständige Induktion
[mm] 2^n\le [/mm] n! [mm] \forall [/mm] n [mm] \in \IN, n\ge [/mm] 4 |
Für andere Beispiel habe ich den Induktionsbeweis verstanden, bei diesem bin ich mir über die Führung jedoch unsicher.
Man beginnt mit dem Induktionsanfang, setzt also n=4: [mm] 16\le [/mm] 24 und dies ist eine wahre Aussage.
Die Induktionsvoraussetzung lautet: [mm] 2^n\le [/mm] n!
die Induktionsbehauptung dann folglich: [mm] 2^{n+1}\le [/mm] (n+1)!
bei dem Beweis beginne ich: [mm] 2^n*2 \le [/mm] n!*(n+1)
das kann man umschreiben zu: [mm] 2^n*2^1\le [/mm] (n+1)!
bzw.: [mm] 2^{n+1}\le [/mm] (n+1)!
und damit wäre ich ja bereits wieder bei der Behauptung angelangt! Jedoch meine ich, dass dieser Beweis so noch nicht vollständig ist.
Was fehlt? Und warum?
Über eine gute Erklärung würde ich mich sehr freuen, denn in der uni wollte der übungsleiter heute nicht auf diese Frage eingehen, da er es auch nicht richtig wusste!
Vielen Dank.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:50 Mo 22.10.2007 | | Autor: | Loddar |
Hallo jura,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !!
Du warst doch auf gutem Wege ... Beginnen wir mit der linken Seite der Induktionsbehauptung (welche zu beweisen wäre) mit [mm] $2^{n+1} [/mm] \ [mm] \le [/mm] \ (n+1)!$ .
[mm] $$2^{n+1} [/mm] \ = \ [mm] 2^n*2^1 [/mm] \ = \ [mm] \red{2^n}*2 [/mm] \ [mm] \red{\le} [/mm] \ [mm] \red{n!}*\blue{2} [/mm] \ [mm] \blue{\le} [/mm] \ [mm] n!*\blue{(n+1)} [/mm] \ = \ ...$$
An der "roten Stelle" habe ich die Induktionsvoraussetzung [mm] $\red{2^n \ \le \ n!}$ [/mm] eingesetzt. Anschließend habe ich noch wie folgt abgeschätzt: [mm] $\blue{2 \ \le \ (n+1)}$ [/mm] (da ja gilt: $n \ [mm] \ge [/mm] \ 4$).
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 06:25 Di 23.10.2007 | | Autor: | jura |
ok, vielen dank!! ich kann deinen beweis eigentlich auch ganz gut nachvollziehen, nur ehrlich gesagt habe ich im matheunterricht noch nie etwas vom abschätzen gehört?! wir haben die induktion eigentlich fast immer mit beispielen von summen behandelt (zb der beweis für die summe über alle n natürlichen zahlen) und dabei ist das prinzip ja immer, dass man die induktionsvoraussetzung hernimmt und auf beiden seiten mit (n+1)- bezogen auf das oben genannte bsp mit der summe- addiert, um so das nachfolgeglied von n zu addieren. durch umformen erhält man dann schließlich die induktionsbehauptung und hat somit bewiesen, dass der satz für alle n gilt. dieses prinzip wollte ich eben auf mein bsp nun auch anwenden- so habe ich auf der linken seite mit 2 multipliziert, um eben den nachfolger von [mm] 2^n [/mm] zu erhalten und auf der rechten seite habe ich mit (n+1) multipliziert, um die fakultät vom nachfolgeglied von n! zu bilden. aber so kann man das anscheinend nicht machen...?! ich verstehe bei deiner lösung des abschätzens noch nicht ganz, wo das prinzip mit dem beweis für den nachfolger n+1 liegt. kannst du mir das evtl nochmal erklären und auch einige andere aufagen zum üben geben, damit ich das mit dem abschätzen auch an anderen bsp selbst üben und so festigen kann?! danke und bis bald.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:46 Di 23.10.2007 | | Autor: | koepper |
Hallo jura,
das Prinzip ist ganz einfach:
Im Induktionsanfang beweist du, daß die Aussage für eine ganz bestimmte Zahl n gilt.
Danach stellst du dir vor (nimmst an), daß die Aussage für irgendein n korrekt ist und versuchst, damit zu beweisen, daß die Aussage auch für n+1 korrekt ist.
Wenn du das geschafft hast, ist die Aussage für alle natürlichen Zahlen ab derjenigen bewiesen, für die du das im Induktionsanfang gezeigt hast:
Ein Beispiel:
Wir haben bewiesen, daß die Aussage für n=4 gilt und wir haben bewiesen, daß wenn die Aussage für irgendein n gilt, daß sie dann auch für n+1 gilt. Setze nun n=4, dann siehst du daß wir damit gezeigt haben, daß die Aussage auch für n=5 korrekt ist.
Da sie aber für n=5 korrekt ist, folgt mit dem gleichen Gedanken, daß sie auch für n=6 korrekt ist, und so weiter...
In dieser Aufgabe hast du den Induktionsanfang korrekt gemacht. Nun zum zweiten Schritt:
Du nimmst an, die Aussage würde für irgendein n bereits gelten (mindestens ein solches n kennen wir ja schon, nämlich n=4)
Nun versuchst du, aus dieser Annahme [mm] $2^n \leq [/mm] n!$ durch Folgerungen die Behauptung für n+1: [mm] $2^{n+1} \leq [/mm] (n+1)!$ zu gewinnen:
Das geht am einfachsten so:
[mm] $\phantom{Leftrightarrow} 2^n \leq [/mm] n! [mm] \quad [/mm] | *2$
[mm] $\Leftrightarrow 2^{n+1} \leq [/mm] n! * 2$
[mm] $\Rightarrow 2^{n+1} \leq [/mm] n! * (n+1)$, denn für $n [mm] \geq [/mm] 4$ ist offensichtlich $n + 1 [mm] \geq [/mm] 2.$
[mm] $\Leftrightarrow 2^{n+1} \leq [/mm] (n+1)!$ und das ist ja im 2. Schritt des Beweises zu zeigen.
Was Loddar dir gezeigt hat, ist im Prinzip genau dasselbe.
Den Gedanken: " denn für $n [mm] \geq [/mm] 4$ ist offensichtlich $n + 1 [mm] \geq [/mm] 2.$ " nennt man auch "abschätzen".
Eine Abschätzung ist nichts weiter, als eine Ungleichung aufzustellen.
Oft ist es in solchen Induktionsbeweisen auch geschickt, sich im Induktionsschritt erst einmal die Behauptung für n+1 hinzuschreiben und dann zu versuchen, davon ausgehend durch Äquivalenzumformungen auf die Behauptung für n zu kommen. Aber Vorsicht: Du mußt in diesem Fall wirklich darauf achten, daß du keine Folgerungen sondern nur Äquivalenzumformungen ausführst, denn am Ende mußt du umgekehrt argumentieren und sagen: Da ich nun bei meiner Induktionsvoraussetzung angekommen bin und alle Umformungen nur Äquivalenzumformungen waren, kann ich nun auch rückwärts argumentieren und von meiner Voraussetzung (gilt für ein n) zur Behauptung (gilt für n+1) zurückkommen.
Alles verstanden?
Gruß
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:39 Di 23.10.2007 | | Autor: | jura |
| Aufgabe | beweis der vollständigen induktion über n [mm] (n\in\IN):
[/mm]
[mm] \summe_{k=1}^{n}(a_{k}+b_{k})=\summe_{k=1}^{n}a_{k}+\summe_{k=1}^{n}b_{k}
[/mm]
|
ja, besten dank!!! das allgemeine prinzip der induktion war mir ja eigentlich schon klar und das neue mit den ungleichungen und dem abschätzen habe ich nun eigentlich auch verstanden- an diesem bsp. wie schon gesagt- bisher habe ich nur andere aufgabentypen gehabt, diese richtung und denkweise ist also neu für mich und deshalb noch einmal die anfrage: hat noch jemand übungsaufgaben oder beispiele für mich, denn je mehr man rechnet und versteht....
ansonsten hätte ich da bereits eine neue aufgabe für den beweis der vollständigen induktion über n [mm] (n\in\IN):
[/mm]
[mm] \summe_{k=1}^{n}(a_{k}+b_{k})=\summe_{k=1}^{n}a_{k}+\summe_{k=1}^{n}b_{k}
[/mm]
für den induktionsanfang setze ich n=1 und erhalte somit [mm] a_{1}+b_{1}=a_{1}+b_{1}
[/mm]
und dies ist eine wahre aussage.
in der induktionsbehauptung setze ich in die voraussetzung für n einfach n+1 ein.
anschließend schreibe ich für den beweis wieder die linke seite der voraussetzung hin und addiere dann [mm] a_{n+1}+b_{n+1} [/mm] .......
ja, da komme ich dann nicht mehr weiter, wenn es denn überhaupt richtig ist bis dahin.
könnt ihr mir einen tipp geben oder den rest erklären?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:58 Di 23.10.2007 | | Autor: | steena |
naja, du musst jetzt erst mal definieren, was rauskommen soll, wenn du n+1 einsetzen würdest, also [mm] \summe_{i=1}^{n+1} [/mm] (a+b) = [mm] \summe_{i=1}^{n+1} [/mm] a [mm] +\summe_{i=1}^{n+1}b.
[/mm]
dann lässt du die rechte seite erstmal so im raum stehen, denn das ist das ergebnis, das bei der umformulierung der linken seite rauskommen soll. und dann nimmst du dir die linke seite vor und formulierst sie so lange um, bis das ergebnis da steht.
kann dir kleider nicht ausführlicher antworten, hab selber noch zeug zu machen bis morgen, sorry!!! aber vll traut sich jetzt auch mal wer anders ran...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:36 Di 23.10.2007 | | Autor: | jura |
kann mir bitte irgendjemand helfen und meine obige frage bearbeiten? sie gilt zwar jetzt im forum als beantwortet, aber diese (fehlerhafte) antwort hilft mir ja nun nicht wirklich großartig weiter....
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:22 Do 25.10.2007 | | Autor: | jura |
der empfänger konnte nix mit anfangen....na das klingt ja nett....in meinem obigen beitrag hab ich doch bereits selbst n+1 eingesetzt.....von daher lieferte mir die antwort nur einfach nix neues. aber egal.
|
|
|
| |
|
| Status: |
(Korrektur) richtig (detailiert geprüft)  | | Datum: | 16:45 Mi 24.10.2007 | | Autor: | leduart |
Hallo
in der Antwort ist kein Fehler, der Empfänger konnte nur nix mit anfangen
Gruss leduart
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:23 Mi 24.10.2007 | | Autor: | koepper |
Hallo jura,
lies am besten noch einmal meinen Beitrag oben.
Im Induktionsschritt gehst du davon aus, daß die Behauptung für ein n gilt (nicht für n+1) und versuchst, durch Folgerungen die Behauptung für n+1 zu gewinnen.
Schreibe also die Behauptung für n hin und addiere auf beiden Seiten [mm] $a_{n+1}$ [/mm] und [mm] $b_{n+1}$.
[/mm]
Denn Rest solltest du dann schon sehen.
Gruß
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:23 Mi 24.10.2007 | | Autor: | jura |
he, wenn du meine letzte frage genau liest, siehst du, dass ich als ansatz für den beweis bereits [mm] a_{n+1}+b_{n+1} [/mm] zu der induktionsvoraussetzung von n addiert habe!!! du gibst mir hier also nicht unbedingt einen neuen tipp....aber zumindest ansporn, mir noch einmal alles anzuschaun, um nicht evtl doch etwas zu "sehen"....mein problem ist nur immer, dass ich mir nicht sicher bin, welche sätze ich bei der umformung anwenden darf, wenn ich gerade einen bestimmten satz beweisen soll....ich habe es trotzdem mal versucht und die summanden vertauscht, das ganze dann ausführlich und somit gut erkennbar ausgeschrieben, um es dann wieder jeweils mit einem summenzeichen zusammenzufassen- und so erhalte ich ja wieder die aussage der induktionsbehauptung für n+1 und der satz ist bewiesen. (?)
ich schreibe nocheinmal alles (zumindest den beweis) auf (auch wenn es seeeeeeeeeehr aufwendig ist), aber ich bin mir besonders bei der "richtigen mathematischen" schreibweise und beweisführung unsicher- würde mich also über eine korrektur sehr freuen!
beweis:
[mm] \summe_{k=1}^{n+1} (a_{k}+b_{k})= \summe_{k=1}^{n} (a_{k}+b_{k})+ a_{n+1}+b_{n+1}= \summe_{k=1}^{n} a_{k}+\summe_{k=1}^{n} b_{k}+ a_{n+1}+b_{n+1}
[/mm]
[mm] =\summe_{k=1}^{n} a_{k}+a_{n+1}+\summe_{k=1}^{n} b_{k}+b_{n+1}
[/mm]
[mm] =a_{1}+a_{2}+.....+a_{n}+a_{n+1}+b_{1}+b_{2}+....+b_{n}+b_{n+1}
[/mm]
[mm] =\summe_{k=1}^{n+1} a_{k}+\summe_{k=1}^{n+1} b_{k}
[/mm]
so, in meinem heft hab ich das ganze nun noch schön farbig markiert, damit man die Voraussetzung und die bewiesene Behauptung schön erkennen kann, jedoch ist mir das hier echt etwas zu umständlich, ich hoffe, du blickst auch so durch.......
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:43 Mi 24.10.2007 | | Autor: | leduart |
Hallo
Deinen Ton den Helfern gegenüber find ich nicht sehr nett!
Aber dein Beweis ist richtig, es kann aber sein da der Beweis ja läppisch ist, dass du zeigen sollst, dass das mit der Definition des Summenzeichens (die vielen Leuten am Anfang Schwierigkeiten macht) übereinstimmt. Dann müsstest du die in deiner Vorlesung nachsehen.
Dazu kommt, dass du die verwendeten "Gesetze angeben solltest:
Du schliesst ja aus a1+b1+a2+b2=a1+a2 +b1+b2 verwendest also as Kommutativgesetz.
Das tust du am Ende wieder, indem du aus [mm] A=\summe_{i=1}^{n}a_i, B=\summe_{i=1}^{n}b_i
[/mm]
[mm] A*B+a_{n+1}+b_{n+1}=A+a_{n+1}+B+b_{n+1} [/mm] schliesst.
diese Ausnutzung des Kommutativgesetzes ist der eigentliche Schritt, und dass man das wie oben benutzt ist die wichtige Aussage.
genau wie der einzig bedeutende Schritt in deinem vorigen Beweis war, dass [mm] n!*2
kurz du musst sagen, warum deine (richtigen) Umformungsschritte richtig sind!
Ich hoff ich krieg jetzt nicht wieder ne Abreibung, weil du das alles schon wusstest
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:33 Do 25.10.2007 | | Autor: | jura |
hey sorry!!!!! ja, einige sätze meinerseits kamen sicher etwas böse rüber- aber das sollten ehrlich in keinster weise abreibungen sein, das kannst du mir glauben! ich bin echt dankbar für dieses forum und die leute, die zeit und mühe investieren, um anderen (wie mir) zu helfen- ist nicht selbstverständlich! beim schreiben geht eben oft die art und weise verloren, WIE etwas gesagt und gemeint ist.....und dann war ich evtl auch leicht gereizt, weil ich schon ne weile dran saß, und dann kommt ne antwort, ich lese sie und es erklärt mir genau das, was ich bereits dastehen hab und worauf ich seit ner weile starre- wahrscheinlich ärgert man sich vor allem über sich selbst....mein ego is so schon angekratzt, wenn ich nicht alles selbst weiß und dann fühle ich mich wohl erst recht sehr schnell als "dummerchen" hingestellt. also wie gesagt, nimms mir bitte nicht übel!
|
|
|
| |
|
Hallo,
Ich glaub Du hast alles richtig gemacht! Tip: Schreibe zuerst das auf, was Du weißt, d.h. IV: (n=1: klar: Häkchen) [mm] 2^{n} \le [/mm] n! und 2 [mm] \le [/mm] (n+1) => IS: [mm] 2^{n+1} \le [/mm] (n+1)! und der Beweis ist klar.
Hoffentlich konnte Deine Frage hiermit aufgelöst werden.
Grüße
Andreas
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 06:29 Di 23.10.2007 | | Autor: | jura |
also n=1 verdient hier kein häkchen!!! setz doch einfach mal ein! es steht ja bereits in der aufgabenstellung, dass [mm] n\ge4
[/mm]
|
|
|
| |
|
dann halt für n gr./gl. 4, also n=4 IA
Danke für den Hinweis.
Gruß
Andreas
|
|
|
|
