Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:16 Di 28.12.2010 | | Autor: | Mousegg |
| Aufgabe | Beweisen Sie auf mindestens zwei verschiedene Weisen:
1.) [mm] \bruch{(n+1)^n} {2^n} [/mm] > n! für n [mm] \ge [/mm] 2 |
Diese Aufgabe ist für mich sehr ungewohnt ,da wir im Moment eigentlich lineare Algebra machen. Ich denke mit zwei verscheidenen Arten des Beweises ist ein direkter und ein Induktionsbeweis gemeint ich hab beides versucht bin aber selbst beim Induktionsbeweis hängen geblieben pbwohl ich zuerst dachte das müsste einfacher sein hab mich dann erst mal bei wikipedia über Fakultät informiert und hab gesehen dass man das ganze auch so schreiben kann
[mm] \bruch {\summe_{i=0}^{n} \vektor{n \\ k} * n^{n-k} *1^k }{\summe_{i=0}^{n} \vektor{n \\ k}} [/mm] > n!
Hat hier vielleicht jemand eine idee wie mand den Beweis direkt führen könnte hab bisher noch keine UMformung gefunden die mir igendwie geholfwen hätte
Hab dann Induktion probiert
IA: sei n=2
[mm] 3^2/2^2 [/mm] =2,25 > 2*1 stimmt also
IV: steht ja bereits in der Aufagebnstellung
IS: Ich hoffe ich mache ihn korrekt
[mm] \bruch {\summe_{i=0}^{n+1} \vektor{n+1 \\ k} * (n+1)^{n+1-k} }{\summe_{i=0}^{n+1} \vektor{n+1 \\ k}}
[/mm]
= [mm] \bruch {\summe_{i=0}^{n} \vektor{n+1\\ k} * (n+1)^{n+1-k} +1} {2*2^n}
[/mm]
Nach IV > [mm] \bruch{1}{2} [/mm] * n!+ [mm] \bruch{1}{2^{n+1}} [/mm]
ich kann doch die IV anwenden da [mm] \bruch{(n+1)^n} {2^n} <\bruch {\summe_{i=0}^{n} \vektor{n+1\\ k} * (n+1)^{n+1-k} }{ 2^n} [/mm] oder ?
Ist das soweit korrekt bin hier sehr unsicher wäre nett wenn sich jemand dass ganze kurz anschauen würde und mir ein paar tipps geben könnte.
Dankeschön
|
|
| |
|
| Status: |
(Antwort) fehlerhaft  | | Datum: | 17:01 Di 28.12.2010 | | Autor: | ggg |
Hi,
Mein Vorschlag wäre, das du beim ersten Teil den Bruch kürzt,
also [mm] \bruch {\summe_{i=0}^{n} \vektor{n \\ k} \cdot{} n^{n-k} \cdot{}1^k }{\summe_{i=0}^{n} \vektor{n \\ k}}= n^{n-k} \cdot{}1^k=n^{n-k}> [/mm] n!.
Es ist einleuchtend das eine Potenz größer als eine Fakultät ist(was man natürlich auch zeigen kann), sodass unmittelbar die Behauptung folgt.
Das noch ein bisschen mathematisch formulieren und zack ist der erste Beweis fertig.
mfg
Jonas
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:11 Di 28.12.2010 | | Autor: | Mousegg |
Bist du sicher das man das so einfach kürzen kann ?? Ich meine das Summenzeichen geht ja über den ausdruck n über k hinaus dh. du hast für jedes k einen anderen faktor ... Ich weiß nicht aber ich glaub nicht dass man dann so einfach die Summe ausklammern kann ... Aber du darfst mich gerne vom gegenteil überzeugen :)
|
|
|
| |
|
> Bist du sicher das man das so einfach kürzen kann ?? Ich
> meine das Summenzeichen geht ja über den ausdruck n über
> k hinaus dh. du hast für jedes k einen anderen faktor ...
> Ich weiß nicht aber ich glaub nicht dass man dann so
> einfach die Summe ausklammern kann ... Aber du darfst mich
> gerne vom gegenteil überzeugen :)
Ne, du hast Recht - das ist wirklich richtig falsch.
Zum eigentlichen Thema: Bei der Induktion würde ich nicht über die Summendarstellung gehen - im Schritt auf n+1 kannst du eigentlich recht "robust" die linke Seite nach unten abschätzen (indem du viele positive Summanden weglässt), so dass sich relativ leicht sehen lässt, dass dort ein Faktor größer als (n+1) mal dem Faktor aus der Induktions-Voraussetzung steht und ist somit bei (n+1)!
lg weightgainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:42 Di 28.12.2010 | | Autor: | Mousegg |
OK erstmal danke für deine Hilfe versuch jetzt mal den weg zu gehen um deinen Tipp nachzuvollziehen dann versuch ich das ganz nochmal ohne summendarstellung :
also
IS:
[mm] \bruch{(n+2)^{n+1}}{2^{n+1}} [/mm] nach IV > [mm] \bruch{(n+2)}{2} [/mm] *n!
da [mm] \bruch{(n+2)^{n}}{2^{n}} [/mm] > [mm] \bruch{(n+1)^{n}}{2^{n}} [/mm] ???
Jetzt muss ich doch weiter zeigen ,dass
[mm] \bruch{(n+2)}{2} [/mm] *n! > (n+1)!
(n+2)*n! > 2*(n+1)!
n*n! +2*n! > 2*(n+1)!
n*n!> 2*(n+1)!-2*n!
n*n!>2*n!(n+1-1)
n*n!>2*n*n!
hmm na gut vermutlich musste ich das nicht zeigen was ist denn hier falsch gelaufen ? Ich glaube ich hab da noch einen bösen Fehler...
Kannst du vielleicht noch nochmal genauer erklären wie ich das ganze nach unten abschätzen kann?
|
|
|
| |
|
> OK erstmal danke für deine Hilfe versuch jetzt mal den weg
> zu gehen um deinen Tipp nachzuvollziehen dann versuch ich
> das ganz nochmal ohne summendarstellung :
>
> also
> IS:
>
> [mm]\bruch{(n+2)^{n+1}}{2^{n+1}}[/mm] nach IV > [mm]\bruch{(n+2)}{2}[/mm]
> *n!
>
Dieser Schritt ist schon falsch, weil deine IV nichts über (n+2) sagt!!! Da musst du schon ein wenig mehr Anstrengungen reinstecken...
> da [mm]\bruch{(n+2)^{n}}{2^{n}}[/mm] > [mm]\bruch{(n+1)^{n}}{2^{n}}[/mm] ???
>
> Jetzt muss ich doch weiter zeigen ,dass
>
Naja, der erste Schritt war schon falsch, also das hier nicht mehr von Belang.
> [mm]\bruch{(n+2)}{2}[/mm] *n! > (n+1)!
> (n+2)*n! > 2*(n+1)!
> n*n! +2*n! > 2*(n+1)!
> n*n!> 2*(n+1)!-2*n!
> n*n!>2*n!(n+1-1)
> n*n!>2*n*n!
>
> hmm na gut vermutlich musste ich das nicht zeigen was ist
> denn hier falsch gelaufen ? Ich glaube ich hab da noch
> einen bösen Fehler...
>
> Kannst du vielleicht noch nochmal genauer erklären wie ich
> das ganze nach unten abschätzen kann?
>
>
>
Naja, vielleicht mache ich das auch zu umständlich, aber auch harte Arbeit führt manchmal zum Ziel (ich benutze übrigens ein Potenzgesetz und schreibe den Exponenten ganz raus an den Bruch):
[mm]\left(\bruch{n+2}{2} \right)^{n+1} = \bruch{n+2}{2} * \left( \bruch{n+2}{2} \right)^{n} = [/mm]
[mm]= \bruch{n+2}{2} * \left( \bruch{n+1}{2} + \bruch{1}{2} \right)^{n} [/mm] | Jetzt Binomische Formel nutzen und nur die ersten beiden Glieder mitnehmen (also abschätzen)
[mm]> \bruch{n+2}{2} * \left( \left( \bruch{n+1}{2} \right)^{n} + n * \left( \bruch{n+1}{2} \right)^{n-1} * \bruch{1}{2} \right) [/mm] | hinteren Teil erweitern, so dass dort auch der Exponent n steht
[mm] = \bruch{n+2}{2} * \left( \left( \bruch{n+1}{2} \right)^{n} + \bruch{n}{2} *\bruch{2}{n+1} * \left( \bruch{n+1}{2} \right)^{n} \right) [/mm] | ich mach mal ein paar Schritte zusammen, kannst du ja einzeln machen
[mm] = \left( n+1+ \bruch{n}{2*(n+1)} \right) * \left( \bruch{n+1}{2} \right)^{n} [/mm] | jetzt IV auf den hinteren Teil anwenden, und die vordere Klammer ist größer als n+1
[mm] > (n+1)*n! = (n+1)![/mm]
So könnte es gehen - wie gesagt, vielleicht gibt es schönere Wege (einen anderen Beweis musst du ja ohnehin noch finden).
lg weightgainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:18 Mi 29.12.2010 | | Autor: | Mousegg |
Wow ok erstmal dankeschön für diesen warscheinlich für dich auch etwas aufwendigeren Beweis ich denke dank deiner Erklärungen hab ich auch alle Schritte verstanden und weiß jetzt besser wie man sowas abschätzen kann...
Das einzige was ich noch nicht ganz verstehe ist wieso ich nicht
[mm] \bruch{(n+2)^n}{2^n} [/mm] durch [mm] \bruch{(n+1)^n}{2^n} [/mm] nach unten abschätzen kann und dann darauf die IV anwenden kann
MIr ist klar das es falsch ist es kommt ja auch Unsinn raus aber wieso ?
|
|
|
| |
|
Hallo,
das liegt schlichtweg daran, dass du zu sehr nach unten abgeschätzt (= verkleinert) hast. dann muss die Voraussetzung nicht mehr stimmen.
Wenn sie aber dennoch gestimmt hätte, dann wäre die zu zeigende Aussage gefolgt.
lg
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:46 Mi 29.12.2010 | | Autor: | Mousegg |
OK gut und woher weiß ich dann dass die abschätzungen von weightgainer nicht auch falsch waren ... bzw weiß man nur das die Abschätzungen nicht zu sehr abweichen wenn am ende die Behauptung folgt .Lässt sich irgendwie beurteilen ab wann eine abschätzung zu eine zu große "differenz" hat?
Das ist alles noch ziemlich neu für mich :)
|
|
|
| |
|
Hi,
es gibt (wie du sicher schon vermutest) keine allgemein gültige Aussage über solche Abschätzungen.
Mir hat in dem Fall geholfen, dass ich das Ziel kannte - ich wollte zum einen ja die IV nutzen, d.h. ich wollte irgendwie diesen Faktor bekommen UND ich wusste, dass ich das noch mit einer Zahl größer als (n+1) multiplizieren muss, um letztlich die Behauptung zu bekommen.
Mein erster Versuch war dann auch, NUR den ersten Term der binomischen Formel zu nutzen, aber das reichte eben nicht aus für die Behauptung. Hätte das mit zwei nicht geklappt, hätte ich evtl. noch den dritten genommen, danach aber hätte ich andere Wege gesucht.
So ist das bei Beweisen halt - was am Ende steht ist das Ergebnis eines meistens längeren Prozesses mit einigen Irrwegen. Abgesehen von einer guten Intuition hilft hier vor allem Erfahrung und ein großes mathematisches Wissen.
Wenn du 10 solcher Induktionsbeweise mit Abschätzungen machst, dann werden dir die nächsten 10 auch deutlich leichter fallen  .
Aber es hilft dabei ungemein, wenn man ein Ziel vor Augen hat, zu dem man hin abschätzen will.
Wenn man "ins Blaue rein" abschätzt, dann kannst du natürlich über die Terme, die du weglässt oder vereinfachst (z.B. n+1 > n oder [mm] \bruch{n}{2} [/mm] < n) Aussagen treffen, die dir dann etwas darüber sagen, wie grob deine Abschätzung war. Und solange du das korrekt machst, bleibt auch alles richtig - nur wie sinnvoll dein Ergebnis dann ist, weiß man nicht.
"Schätze die Anzahl der Menschen ab, die jemals auf der Erde gelebt haben."
Nicht so sinnvolle Abschätzung:
"Naja, mehr als 2 werden es schon gewesen sein"
lg weightgainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:17 Mi 29.12.2010 | | Autor: | Mousegg |
^^ ok ich denke jetzt hab ich den Unterschied zwischen einer guten und einer schlechten Abschätzung verstanden ;)
Vielen dank nochmal für die Hilfe jetzt kann der nächste Induktionsbeweis kommen ...
ICh versuch jetzt noch einen direkten Beweis zu finden...
|
|
|
| |
|
Hi,
> Hi,
> Mein Vorschlag wäre, das du beim ersten Teil den Bruch
> kürzt,
Das ist mit Sicherheit KEINE gute Idee.... dazu fällt mir der zwar etwas demotivierende, aber doch immer wieder richtige Spruch ein: "Summen kürzen nur die ...."
(das ist also falsch!)
> also [mm]\bruch {\summe_{i=0}^{n} \vektor{n \\ k} \cdot{} n^{n-k} \cdot{}1^k }{\summe_{i=0}^{n} \vektor{n \\ k}}= n^{n-k} \cdot{}1^k=n^{n-k}>[/mm]
> n!.
>
> Es ist einleuchtend das eine Potenz größer als eine
Das ist doch auch Quatsch, so allgemein formuliert sowieso, aber auch wenn man es wohlwollend liest, ist es eben nicht einleuchtend (sogar falsch), vergleiche z.B. mal [mm] n^{1} [/mm] und n!
> Fakultät ist(was man natürlich auch zeigen kann), sodass
Den Beweis würden dann bestimmt gerne alle sehen.
> unmittelbar die Behauptung folgt.
> Das noch ein bisschen mathematisch formulieren und zack
> ist der erste Beweis fertig.
>
> mfg
> Jonas
Eine wichtige Sache wirst du dann in deinem bald beginnenden Mathe-Studium lernen: Sorgfalt [vielleicht kein Trost: Ich bin auch schon voll auf die Nase gefallen, obwohl ich mir sicher war.... ich war dann für entsprechende Hinweise immer dankbar....]
lg weightgainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:04 Di 28.12.2010 | | Autor: | ggg |
Ohh, dann habe ich ein sehr gutes Beispiel geliefert wie man es gerade nicht machen sollte.
Danke für eure Kritik und Hinweise.
mfg
Jonas
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:01 Do 30.12.2010 | | Autor: | Mousegg |
Hab jetzt möglicherweise einen direkten Beweis gefunden die Frage ist nur ob das auch alles Mathematisch korrekt ist :
Also man sollte zeigen ,dass:
[mm] \bruch{\summe_{k=0}^{n}\vektor{n \\ k}*n^{n-k}}{\summe_{k=0}^{n}\vektor{n \\ k}} [/mm] > n!
[mm] \gdw \summe_{k=0}^{n}\vektor{n \\ k}*n^{n-k} [/mm] > [mm] n!*\summe_{k=0}^{n}\vektor{n \\ k}
[/mm]
wenn man jetzt durch n! teilt
[mm] \gdw \bruch{1}{n!}+\summe_{k=1}^{n}\bruch{1}{k!*(n-k)!}*n^{n-k}>\summe_{k=0}^{n}\vektor{n \\ k}
[/mm]
jetzt hab ich die linke Summe auf beiden Seiten abgezogen
[mm] \gdw [/mm] 0> [mm] \summe_{k=0}^{n}\vektor{n \\ k}- \bruch{1}{n!}-\summe_{k=1}^{n}\bruch{1}{k!*(n-k)!}*n^{n-k}
[/mm]
da die beiden Summen ja immer paarweise den selben Nenner haben kann man sie auch jeweils paarweise abziehen dh. wenn man nur den zähler Betrachtet
[mm] n!-n^{n-1}+....+n!-1
[/mm]
Und während ich das hier schreibe merke ich dass es ziemlich voreilig war das einen BEweis zu nennen ,da man ja gar nicht mit Sicherheit sagen kann das diese Summe immer kleienr 0 ist
Hat also vielleicht jemand eine andere Idee? oder wenigstens einen Tipp?
|
|
|
| |
|
Hi,
ich hab es dieses Mal nicht vollständig aufgeschrieben, aber eigentlich müsste folgende Idee klappen:
1. Links hab ich wieder [mm] \left( \bruch{n+1}{2} \right)^{n}[/mm] geschrieben. Damit habe ich links und rechts gleich viele Faktoren.
2. Ich hab mir für n=4 und 5 mal die Zahlen aufgeschrieben. Die Faktoren links sind ja immer gleich, rechts werden sie immer kleiner. Dabei sieht man, dass sie "genau in der Mitte" gleich groß sind.
3. Ausgehend von der Mitte nimmt man jetzt die nächsten beiden Faktoren (einer nach oben, einer nach unten) und vergleicht deren Produkt. Das ist auf der linken Seite immer größer.
Beispiel (n=4):
Links steht immer 2,5 als Faktor.
Rechts steht [mm]4*3*2*1[/mm]
[mm]2,5^{2} > 3*2[/mm] und [mm]2,5^{2} > 4*1[/mm]
Bei n=5:
Links steht immer 3 als Faktor.
Rechts steht [mm]5*4*3*2*1[/mm]
Der Wert in der Mitte ist gleich, ab da sind die Produkte rechts jeweils kleiner als 9.
Meiner Ansicht nach muss man das jetzt nur "ordentlich" mit "n-Termen" aufschreiben. Für die mittleren ist das leicht, nur die Verallgemeinerung auf ALLE Paare hab ich nicht mehr gemacht:
Für n gerade:
RECHTS:
[mm] \bruch{n}{2}* \left( \bruch{n}{2} + 1 \right) = \bruch{n^{2}}{4} + \bruch{n}{2} [/mm]
LINKS:
[mm] \bruch{n+1}{2} * \bruch{n+1}{2} = \bruch{n^{2}}{4} + \bruch{n}{2} + \bruch{1}{4} [/mm]
Eigentlich muss man nur rechts die beiden Zahlen anpassen würde ich sagen.
Auch dieser Beweis strotzt nicht gerade vor Eleganz, er nutzt simple Beziehungen zwischen den Zahlen.
Mein Grundproblem, wenn ich links die binomischen Formeln nutze: Ich muss dann eine Summe mit einem Produkt vergleichen und das kann ich nicht so gut, da habe ich kein Gefühl für.
Für möglicherweise elegantere Beweise fehlt mir dann das mathematische Rüstzeug....
lg weightgainer
|
|
|
|
