Fehler im Beweis < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
Hallo zusammen
Habe ein Problem mit folgendem Beweis:
Für alle [mm] k\in\IN_{0} [/mm] und [mm] n\in\IN [/mm] gilt:
[mm] \vektor{n \\ k}*\bruch{1}{n^{k}} \le \bruch{1}{k!}
[/mm]
Mein Lösungsansatz:
[mm] \vektor{n \\ k}*\bruch{1}{n^{k}} [/mm] = [mm] \bruch{n!}{k!(n-k)!}*\bruch{1}{n^{k}} [/mm] = [mm] \bruch{n*(n-1)*(n-2)*...*1}{n^{k}*k!*(n-k)*(n-k-1)*...*1)} [/mm] = [mm] \bruch{n*(n-1)*...*(n-k+1)}{n^{k}*k!} [/mm]
Da [mm] n^{k} \ge [/mm] 1
[mm] \Rightarrow \bruch{n*(n-1)*...*(n-k+1)}{n^{k}*k!} \le \bruch{n*(n-1)*...*(n-k+1)}{k!} \ge \bruch{1}{k!} [/mm] !!!!
Welche Überlegung ist falsch???
Liebe Grüsse
|
|
| |
|
> Hallo zusammen
>
> Habe ein Problem mit folgendem Beweis:
> Für alle [mm]k\in\IN_{0}[/mm] und [mm]n\in\IN[/mm] gilt:
> [mm]\vektor{n \\ k}*\bruch{1}{n^{k}} \le \bruch{1}{k!}[/mm]
>
> Mein Lösungsansatz:
> [mm]\vektor{n \\ k}*\bruch{1}{n^{k}}[/mm] =
> [mm]\bruch{n!}{k!(n-k)!}*\bruch{1}{n^{k}}[/mm] =
> [mm]\bruch{n*(n-1)*(n-2)*...*1}{n^{k}*k!*(n-k)*(n-k-1)*...*1)}[/mm]
> = [mm]\bruch{n*(n-1)*...*(n-k+1)}{n^{k}*k!}[/mm]
> Da [mm]n^{k} \ge[/mm] 1
> [mm]\Rightarrow \bruch{n*(n-1)*...*(n-k+1)}{n^{k}*k!} \blue{\le} \bruch{n*(n-1)*...*(n-k+1)}{k!} \green{\ge} \bruch{1}{k!}[/mm]
> !!!!
>
> Welche Überlegung ist falsch???
Hallo,
die letzte Zeile stimmt nicht. Du schätzt dort in verschiedene Richtungen ab.
(Daraus, daß 4<5 und 5>3, kannst Du nicht 4<3 folgern.)
LG Angela
>
> Liebe Grüsse
|
|
|
| |
|
Hallo Angela!
Folgendes ist doch richtig (oder?):
Da [mm] n^{k} \ge [/mm] 1
[mm] \Rightarrow \bruch{n*(n-1)*...*(n-k+1)}{n^{k}*k!} \blue{\le} \bruch{n*(n-1)*...*(n-k+1)}{k!}
[/mm]
Aber wie kann ich nun zeigen, dass dies [mm] \le\bruch{1}{k!} [/mm] ?
Liebe Grüsse
|
|
|
| |
|
> Hallo Angela!
> Folgendes ist doch richtig (oder?):
> Da [mm]n^{k} \ge[/mm] 1
> [mm]\Rightarrow \bruch{n*(n-1)*...*(n-k+1)}{n^{k}*k!} \le \bruch{\blue{n*(n-1)*...*(n-k+1)}}{k!}[/mm]
>
Hallo,
diese Abschätzung ist richtig.
> Aber wie kann ich nun zeigen, dass dies [mm]\le\bruch{1}{k!}[/mm] ?
Es wird Dir mit obiger Abschätzung nicht gelingen, denn der Nenner ist nunmal größer als 1.
Pack es mal komplett anders an:
[mm] \bruch{n*(n-1)*...*(n-k+1)}{n^{k}*k!}=\bruch{n}{n}*\bruch{n-1}{n}*...*\bruch{n-k+1}{n}*\bruch{1}{k!} [/mm] ...
LG Angela
|
|
|
| |
|
> > Hallo Angela!
> > Folgendes ist doch richtig (oder?):
> > Da [mm]n^{k} \ge[/mm] 1
> > [mm]\Rightarrow \bruch{n*(n-1)*...*(n-k+1)}{n^{k}*k!} \le \bruch{\blue{n*(n-1)*...*(n-k+1)}}{k!}[/mm]
> > Aber wie kann ich nun zeigen, dass dies [mm]\le\bruch{1}{k!}[/mm] ?
Du kannst doch, richtig besehen, nicht einmal hoffen,
dass es gelingt zu zeigen, dass ein Term einen kleinen
Wert hat, wenn du statt des eigentlichen Bruchterms
einen neuen bastelst, indem du aus dem alten einen
potentiell sehr, sehr großen Faktor einfach entfernst.
Analog dazu wäre etwa, wenn du zeigen möchtest,
dass ein Millimeter kleiner als ein Zoll ist, indem du
zunächst mal auf das "Milli" in "Millimeter" verzichtest
und dann zeigen möchtest, dass ein Meter kleiner als
ein Zoll ist. Wäre ein Meter tatsächlich kürzer als ein
Zoll, dann hättest du zwar dein Ziel erreicht, denn
ein Millimeter wäre dann ebenfalls garantiert kleiner
als ein Zoll. Aber die Realität sieht halt ein wenig
anders aus ...
LG , Al-Chw.
|
|
|
| |
|
Ahaaa....
[mm] \bruch{n*(n-1)*...*(n-k+1)}{n^{k}*k!}=\bruch{n}{n}*\bruch{n-1}{n}*...*\bruch{n-k+1}{n}*\bruch{1}{k!} [/mm] = [mm] (1-\bruch{1}{n})*(1-\bruch{2}{n})*...*(1-\bruch{k-1}{n})*\bruch{1}{k!}
[/mm]
Da alle Brüche (ausser [mm] \bruch{1}{k!}) [/mm] < 1
[mm] \Rightarrow (1-\bruch{1}{n})*(1-\bruch{2}{n})*...*(1-\bruch{k-1}{n})*\bruch{1}{k!} [/mm] < [mm] \bruch{1}{k!} [/mm]
Jetzt habe ich aber ein < und nicht ein [mm] \le [/mm] !?
|
|
|
| |
|
Hallo Babybel73,
> Ahaaa....
>
> [mm]\bruch{n*(n-1)*...*(n-k+1)}{n^{k}*k!}=\bruch{n}{n}*\bruch{n-1}{n}*...*\bruch{n-k+1}{n}*\bruch{1}{k!}[/mm]
> =
> [mm](1-\bruch{1}{n})*(1-\bruch{2}{n})*...*(1-\bruch{k-1}{n})*\bruch{1}{k!}[/mm]
> Da alle Brüche (ausser [mm]\bruch{1}{k!})[/mm] < 1
> [mm]\Rightarrow (1-\bruch{1}{n})*(1-\bruch{2}{n})*...*(1-\bruch{k-1}{n})*\bruch{1}{k!}[/mm]
> < [mm]\bruch{1}{k!}[/mm]
>
> Jetzt habe ich aber ein < und nicht ein [mm]\le[/mm] !?
>
Überlege, ob es ein k geben kann,
für das Gleichheit herrscht.
Gibt es ein solches k,
dann hast Du auch ein [mm]\le[/mm].
Gruss
MathePower
|
|
|
| |
|
> Jetzt habe ich aber ein < und nicht ein [mm]\le[/mm] !?
Das ist gerade noch etwas zur Logik eines Beweises
einer Ungleichung.
Wenn es dir gelingt, anstelle eines Beweises einer
Ungleichung der Form
$\ T(n)\ [mm] \le\ [/mm] C$
einen Beweis für die Aussage $\ T(n)\ <\ C$ zu finden,
dann ist damit natürlich auch der gefragte Beweis
im Wesentlichen geführt, denn aus der Aussage
$\ T(n)\ <\ C$
folgt natürlich sofort auch die Aussage
$\ T(n)\ [mm] \le\ [/mm] C$
Für die Allgemeingültigkeit der Aussage $\ T(n)\ [mm] \le\ [/mm] C$
ist im Übrigen auch überhaupt nicht erforderlich,
dass es auch gewisse n gibt, für welche die
Gleichheit, also $\ T(n)\ =\ C$ , gültig ist.
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:23 Di 08.10.2013 | | Autor: | Babybel73 |
Hallo zusammen
Vielen Dank euch allen! :)
Bin bereits am nächsten Beweis. Vielleich kommt später nochmal eine Frage! ;) (Natürlich in einem neuen Artikel)
Liebe Grüsse
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:23 Fr 11.10.2013 | | Autor: | Marcel |
Hallo,
> > Jetzt habe ich aber ein < und nicht ein [mm]\le[/mm] !?
>
>
> Das ist gerade noch etwas zur Logik eines Beweises
> einer Ungleichung.
>
> Wenn es dir gelingt, anstelle eines Beweises einer
> Ungleichung der Form
>
> [mm]\ T(n)\ \le\ C[/mm]
>
> einen Beweis für die Aussage [mm]\ T(n)\ <\ C[/mm] zu finden,
> dann ist damit natürlich auch der gefragte Beweis
> im Wesentlichen geführt, denn aus der Aussage
>
> [mm]\ T(n)\ <\ C[/mm]
>
> folgt natürlich sofort auch die Aussage
>
> [mm]\ T(n)\ \le\ C[/mm]
nur mal, damit das nicht einfach so im Raum stehenbleibt:
Die Aussage
[mm] $A\,$ [/mm] oder [mm] $B\,$
[/mm]
ist genau dann wahr, wenn mindestens eine der beiden aufgeführten
Aussagen wahr ist.
Insbesondere gilt also, dass aus der Wahrheit von [mm] $A\,$ [/mm] die Wahrheit der
Aussage [mm] $(A\;\vee \;B)$ [/mm] folgt.
Und [mm] $T(n)\;\le\;C$ [/mm] steht halt für
[mm] $T(n)\;<\;C$ [/mm] oder [mm] $T(n)\;=\;C.$
[/mm]
(Es gilt also
[mm] $T(n)\;<\;C$ $\Longrightarrow$ [/mm] $T(n) [mm] \;\le\;C$
[/mm]
und auch
[mm] $T(n)\;=\;C$ $\Longrightarrow$ $T(n)\;\le\;C.$
[/mm]
Falsch ist (i.a.) aber etwa
[mm] $T(n)\;\le\;C$ $\Longrightarrow$ $T(n)\;<\;C.$)
[/mm]
P.S. Auch hier sei daran erinnert, dass [mm] $A\,$ [/mm] kurz für "Die Aussage [mm] $A\,$ [/mm] ist
wahr" steht, und [mm] $\neg [/mm] A$ würde für "(die zu [mm] $A\,$ [/mm] gehörige Negation) ist
wahr" bzw. [mm] "$A\,$ [/mm] ist falsch" oder [mm] "$A\,$ [/mm] ist nicht wahr" stehen...
So könnte man $2 [mm] \;<\; 5\,$ [/mm] auch als [mm] $\neg(2 \;\ge\; [/mm] 5)$ schreiben... (oder $x [mm] \;<\; 5\,$ [/mm] auch als
[mm] $\neg(x \;\ge\; [/mm] 5)$ ...)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:55 Di 08.10.2013 | | Autor: | Marcel |
Hallo,
> Hallo zusammen
>
> Habe ein Problem mit folgendem Beweis:
> Für alle [mm]k\in\IN_{0}[/mm] und [mm]n\in\IN[/mm] gilt:
> [mm]\vektor{n \\ k}*\bruch{1}{n^{k}} \le \bruch{1}{k!}[/mm]
nur mal als Tipp:
[mm] $\iff [/mm] {n [mm] \choose [/mm] k} [mm] \le \frac{n}{k}*\frac{n}{k-1}*...*\frac{n}{1}$
[/mm]
Und die linke Seite kannst Du schreiben als
${n [mm] \choose k}=\frac{n*(n-1)*...*(n+1-k)}{k!}=\frac{n}{k}*\frac{n-1}{k-1}*...*\frac{n+1-k}{1}$
[/mm]
Damit wird alles "offensichtlich". (Wenn Du es "schöner schreiben willst",
so kannst Du das Produktzeichen [mm] $\prod_{k=1}^n [/mm] ...$ verwenden - straight forward
etwa so:
${n [mm] \choose k}=\prod_{k=1}^n \frac{n+1-k}{k} \le \prod_{k=1}^n [/mm] ...$)
P.S. Den ganzen Beweis kann man eigentlich führen, indem man die
Überlegungen an einem Beispiel führt und sie dann verallgemeinert:
${11 [mm] \choose 5}=\frac{11*10*...*\overbrace{(11+1-5)}^{=7}}{5!} \; \le \; \frac{11*11*...*11}{5!}=\frac{11^5}{5!}$
[/mm]
[mm] $\Longrightarrow [/mm] ...$
Gruß,
Marcel
|
|
|
|
