Induktion: Bin.Koef. < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 17:39 Fr 03.12.2010 | | Autor: | el_grecco |
Eingabefehler: "\left" und "\right" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| Aufgabe | Die folgende Aussage soll mit einem Induktionsbeweis gezeigt werden:
$\underset{n \in \IN_{0}}{\forall}\left( \underset{k \in \IN_{0} : k \le n}{\forall}{n \choose k}=\bruch{n!}{k!(n-k)!}\right)$ |
Hallo,
ich bitte um Korrektur meiner Lösung:
Induktionsanfang $n=0$: ${0 \choose k}=\bruch{0!}{k!(0-k)!}\right)=\begin{cases} 1, & \mbox{für } k=0 \\ \mbox{nicht definiert }, & \mbox{für } k>0 \end{cases}$
Induktionsschritt: $n \to n+1$
Induktionsvoraussetzung: Für ein $n \in \IN$ gelte:
${n \choose k}=\bruch{n!}{k!(n-k)!}$
Zu zeigen:
${n+1 \choose k}=\bruch{(n+1)!}{k!((n+1)-k)!}$
Dann folgt:
${n+1 \choose k}={n \choose k}+{n \choose k-1}=$
$=\bruch{n!}{k!(n-k)!}+\bruch{n!}{(k-1)!(n-(k-1))!}=\bruch{n!}{k!(n-k)!}+\bruch{n!}{(k-1)!(n-k+1)!}=$
$=\bruch{n!(k-1)!(n-k+1)!}{k!(n-k)!(k-1)!(n-k+1)!}+\bruch{n!k!(n-k)!}{(k-1)!(n-k+1)!k!(n-k)!}=...$
Mein letzter Schritt gibt mir etwas zu denken...
Vielen Dank.
Gruß
el_grecco
EDIT:
Hier die Definition wie von leduart verlangt:
For each $n,k \in \IN_{0}$ with $k \le n:$
${n \choose k}=\bruch{n!}{k!(n-k)!}$
Moreover, for $n \ge 1$, one has ${n \choose k}= \# \mathcal P_{k}(\{1,...,n\})$, where $\mathcal P_{k}(A):=\{ B \in \mathcal P(A): \#B=k \}$
denotes the set of all subsets of a set A that have precisely k elements.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:46 Fr 03.12.2010 | | Autor: | ullim |
Hi,
Du bist sicher das Du [mm] \binom{n}{k}=\br{n!}{k!(n-k)!} [/mm] beweisen sollst. Das ist doch eine Definition, die kann man nicht beweisen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:50 Fr 03.12.2010 | | Autor: | el_grecco |
Hallo ullim,
es steht exakt so auf dem Übungsblatt geschrieben. 
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:56 Fr 03.12.2010 | | Autor: | ullim |
Hi,
also ich bin der Meinung das ist Quatsch.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:02 Fr 03.12.2010 | | Autor: | el_grecco |
Hallo ullim,
die Leute machen zwar ab und zu kleinere Leichtsinnsfehler in den Übungsblättern, aber ich traue es ihnen nicht zu, dass sie eine total sinnlose Aufgabe stellen. 
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:07 Fr 03.12.2010 | | Autor: | ullim |
Hi,
dann haben sie jetzt damit den Anfang gemacht. Wer´weiss in welcher Kneipe die Aufgabe entstanden ist. Aber mal im ernst, schau ![[]](/images/popup.gif) hier nach, da steht die Definition auch.
Vielleicht ist ja doch was anderes gemeint?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:14 Fr 03.12.2010 | | Autor: | el_grecco |
Hi ullim,
> Wer´weiss
> in welcher Kneipe die Aufgabe entstanden ist.
![[prost]](/images/smileys/prost.gif "[prost]")
Würde mich nicht wundern. Die Bezahlung für's Assistenzpersonal soll ja nicht die beste sein, was wohl auch Auswirkungen auf die Arbeitsmoral hat...
> Vielleicht ist ja doch was anderes gemeint?
Vielleicht laden die in naher Zukunft ein "Update" hoch, so wie bisher immer bei den Leichtsinnsfehlern.
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:28 Sa 04.12.2010 | | Autor: | leduart |
Hallo Ullim
Nein, das kann man als Def nehmen, ist aber nicht die orsprüngliche, was er beweisen soll ist also nicht Blödsinn sondern die Übereinstimmung von 2 möglichen Def.
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:12 Sa 04.12.2010 | | Autor: | el_grecco |
Guten Mittag!
Diese Aufgabe macht mich echt fertig.
Hoffentlich hat ullim nicht Recht, denn sonst wäre es um das Niveau des Lehrpersonals schon sehr traurig bestellt.
Falls jemand mit dieser Aufgabe etwas anfangen kann, bin ich um jeden Hinweis sehr dankbar.
Investiert aber bitte nicht zuviel Zeit in die Aufgabe, denn das möchte ich niemandem zumuten, denn womöglich ist die Aufgabe tatsächlich fehlerhaft.
Vielen Dank.
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:26 Sa 04.12.2010 | | Autor: | leduart |
Hallo
es kommt einfach darauf an, wie man [mm]\vektor{n \\
k}[/mm] definiert hat.
man kann es über die Formel defnieren oder wie etwa in der Statistik:
Die Anzahl der k elementigen Teilmengen einer n elementigen Menge.
Was ist eure Def?
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:23 Sa 04.12.2010 | | Autor: | el_grecco |
Hallo leduart und danke für deinen Zeiteinsatz und deine Mühe!
Ich habe die Definition zur besseren Übersicht in der Frage selbst ergänzt.
Es handelt sich übrigens um die Vorlesung "Analysis I für Informatiker und Statistiker".
Gruß
el_grecco
|
|
|
| |
|
Hallo,
die erste Frage ist nachwievor aktuell, damit der Thread aber nicht untergeht, starte ich diese "Frage".
Danke
&
Gruß an alle Helfer (m/w)!
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:48 Sa 04.12.2010 | | Autor: | leduart |
Hallo
Wenn ihr wirklich die definition, die du als erstes zitiert hast hattet, ist wirklich nichts zu beweisen,
Wenn ihr die def die nach moreover steht habtm musst du die zum beweis also der induktion verwenden.
Ist die aufgabe so wie sie da steht wörtlich, also ohne weitere Vors oder Rahmen gestellt?
bis dann lula
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:01 Sa 04.12.2010 | | Autor: | el_grecco |
Hallo leduart,
ich habe einige Zeit im Internet gestöbert und dabei das entdeckt:
Link-Text
Ab Seite 54.
Das scheint mir exakt die gleiche Aufgabe zu sein. Wie siehst Du das?
Danke
&
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:08 So 05.12.2010 | | Autor: | ullim |
Hi,
in Deinem Link ist [mm] \binom{n}{k} [/mm] jetzt rekursiv definiert durch
(1) [mm] \binom{0}{0}=1
[/mm]
(2) [mm] \binom{n}{k}=0 [/mm] wenn k<0 oder k>n
(3) [mm] \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}
[/mm]
Das ist natürlich eine andere Voraussetzzung als in Deinem ersten Post. In diesem Fall kann man sehr wohl einen Beweis führen, dass [mm] \binom{n}{k}=\br{n!}{k!*(n-k)!} [/mm] gilt, ist in dem Text ja auch angegeben.
Natürlich stimmt auch die Aussage von Leduart. Wenn [mm] \binom{n}{k} [/mm] definiert ist als die Anzahl von Möglichkeiten , aus einer Menge von n Elementen genau k Elemente ohne Wiederholung und ohne Berücksichtigung der Reihenfolge zu entnehmen, dann ist auch was zu beweisen.
Ich habe nochmal in meinen alten Vorlesungs Unterlagen nachgeschlagen, da wurde der Binomialkoeffizient definiert durch [mm] \binom{n}{k}=\br{n!}{k!*(n-k)!} [/mm] und dann ist eben nichts mehr zu beweisen.
Deiner ergänzten Definition würde ich jetzt aber entnehmen, dass [mm] \binom{n}{k}=\br{n!}{k!*(n-k)!} [/mm] die Definition ist und $ {n [mm] \choose [/mm] k}= [mm] \# \mathcal P_{k}(\{1,...,n\}) [/mm] $ eine zu beweisende Schlussfolgerung ist.
|
|
|
| |
|
| Aufgabe | Die folgende Aussage soll mit einem Induktionsbeweis gezeigt werden:
[mm] $\underset{n \in \IN_{0}}{\forall}\left( \underset{k \in \IN_{0} : k \le n}{\forall}{n \choose k}=\bruch{n!}{k!(n-k)!}\right)$ [/mm] |
Hallo,
ich habe einige Verständnisprobleme bei manchen Zwischenschritten und es wäre sehr nett, wenn jemand darauf eingehen könnte:
${n+1 [mm] \choose [/mm] k}={n [mm] \choose [/mm] k}+{n [mm] \choose [/mm] k-1}=$
[mm] $=\bruch{n!}{(n-k)!k!}+\bruch{n!}{(n-(k-1))!(k-1)!}$
[/mm]
[mm] $=\bruch{n!}{(n-k)!k!}+\bruch{n!}{(n-k+1)!(k-1)!}$
[/mm]
[mm] $=\bruch{n!(n-k+1)}{(n-k+1)(n-k)!k!}+\bruch{n!k}{(n-k+1)!(k-1)!k}$ [/mm] Erweitern
[mm] $=\bruch{n!(n-k+1)}{(n-k+1)k!}+\bruch{n!k}{(n-k+1)!k!}$ [/mm] Definition der Fakultät
[mm] $=\bruch{n!(n-k+1)+n!k}{(n-k+1)k!}$ [/mm] Zusammenfassen der Brüche
[mm] $=\bruch{n!(n-k+1+k)}{(n-k+1)!k!}$ [/mm] Herausheben
[mm] $=\bruch{n!(n+1)}{(n+1-k)!k!}$ [/mm] Addieren
[mm] $=\bruch{(n+1)!}{(n+1-k)!k!}$ [/mm] Definition der Fakultät
Im Schritt "Erweitern" hätte ich so erweitert:
[mm] $=\bruch{n!(n-k+1)!(k-1)!}{(n-k+1)!(k-1)!(n-k)!k!}+\bruch{n!(n-k)!k!}{(n-k+1)!(k-1)!(n-k)!k!}$
[/mm]
Warum wurde anders erweitert bzw. warum ist das wie erweitert wurde richtig?
Im Schritt "Definition der Fakultät" sehe ich leider nicht, was da genau gemacht wurde...?
Der Rest ist soweit klar.
Vielen Dank für die Mühe.
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:55 Di 07.12.2010 | | Autor: | leduart |
Hallo
Bist du denn jetzt sicher, dass ihr diese rekursive Definition der Binomialkoeffizienten hattet, du also den Beweis brauchst?
> Die folgende Aussage soll mit einem Induktionsbeweis
> gezeigt werden:
>
> [mm]\underset{n \in \IN_{0}}{\forall}\left( \underset{k \in \IN_{0} : k \le n}{\forall}{n \choose k}=\bruch{n!}{k!(n-k)!}\right)[/mm]
weiterhin sinnlos, ohne die Angabe wie das [mm] \vektor{n\\k} [/mm] definiert ist.
> Hallo,
>
> ich habe einige Verständnisprobleme bei manchen
> Zwischenschritten und es wäre sehr nett, wenn jemand
> darauf eingehen könnte:
>
> [mm]{n+1 \choose k}={n \choose k}+{n \choose k-1}=[/mm]
>
> [mm]=\bruch{n!}{(n-k)!k!}+\bruch{n!}{(n-(k-1))!(k-1)!}[/mm]
>
> [mm]=\bruch{n!}{(n-k)!k!}+\bruch{n!}{(n-k+1)!(k-1)!}[/mm]
>
> [mm]=\bruch{n!(n-k+1)}{(n-k+1)(n-k)!k!}+\bruch{n!k}{(n-k+1)!(k-1)!k}[/mm]
> Erweitern
erweitern mit dem Ziel von gleichen Nennern. im ersten fehlt zu (n-k+1) Fakultät (n-k+1) das bedeutet unten Def der Fakultat (n+1)!=n!*(n+1)
im 2 ten Bruch aus (k-1)! k! erzeugen
> [mm]=\bruch{n!(n-k+1)}{(n-k+1)k!}+\bruch{n!k}{(n-k+1)!k!}[/mm]
> Definition der Fakultät
oben erklärt
> [mm]=\bruch{n!(n-k+1)+n!k}{(n-k+1)k!}[/mm] Zusammenfassen der
> Brüche
>
> [mm]=\bruch{n!(n-k+1+k)}{(n-k+1)!k!}[/mm] Herausheben
>
> [mm]=\bruch{n!(n+1)}{(n+1-k)!k!}[/mm] Addieren
>
> [mm]=\bruch{(n+1)!}{(n+1-k)!k!}[/mm] Definition der Fakultät
siehe oben
> Im Schritt "Erweitern" hätte ich so erweitert:
>
> [mm]=\bruch{n!(n-k+1)!(k-1)!}{(n-k+1)!(k-1)!(n-k)!k!}+\bruch{n!(n-k)!k!}{(n-k+1)!(k-1)!(n-k)!k!}[/mm]
das ist nicht falsch aber nicht Zielstrebig.
> Warum wurde anders erweitert bzw. warum ist das wie
> erweitert wurde richtig?
weil oben und unten derselbe Faktor hinzukam!
> Im Schritt "Definition der Fakultät" sehe ich leider
> nicht, was da genau gemacht wurde...?
Gruss leduart
>
|
|
|
| |
|
Hallo,
ich gehe jetzt einfach den Weg wie in dem Lehrbuch angegeben. Im besten Fall ist es richtig, wenn es falsch ist, habe ich etwas dazugelernt.
leduart, ich habe mir Deine Ausführungen mehrmals durchgelesen, aber die besagten Stellen "Erweitern" und "Definition der Fakultät" bereiten mir leider noch immer Probleme.
Der "magische" Schlüssel dürfte wohl $(n+1)!=n!*(n+1)$ sein, aber ich sehe nicht, wie aus [mm] $(n-k+1)\*(n-k)!\*k!$ [/mm] dann folgt [mm] $(n-k+1)\*k!$ [/mm] ![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]")
[mm]{n+1 \choose k}={n \choose k}+{n \choose k-1}=[/mm]
[mm]=\bruch{n!}{(n-k)!k!}+\bruch{n!}{(n-(k-1))!(k-1)!}[/mm]
[mm]=\bruch{n!}{(n-k)!k!}+\bruch{n!}{(n-k+1)!(k-1)!}[/mm]
[mm]=\bruch{n!(n-k+1)}{(n-k+1)(n-k)!k!}+\bruch{n!k}{(n-k+1)!(k-1)!k}[/mm] Erweitern
> erweitern mit dem Ziel von gleichen Nennern. im ersten
> fehlt zu (n-k+1) Fakultät (n-k+1) das bedeutet unten Def
> der Fakultat (n+1)!=n!*(n+1)
> im 2 ten Bruch aus (k-1)! k! erzeugen
[mm]=\bruch{n!(n-k+1)}{(n-k+1)k!}+\bruch{n!k}{(n-k+1)!k!}[/mm] Definition der Fakultät
[mm]=\bruch{n!(n-k+1)+n!k}{(n-k+1)k!}[/mm] Zusammenfassen der Brüche
[mm]=\bruch{n!(n-k+1+k)}{(n-k+1)!k!}[/mm] Herausheben
[mm]=\bruch{n!(n+1)}{(n+1-k)!k!}[/mm] Addieren
[mm]=\bruch{(n+1)!}{(n+1-k)!k!}[/mm] Definition der Fakultät
Hoffe Du erkennst mein Problem...
Vielen Dank
&
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:12 Do 09.12.2010 | | Autor: | leduart |
>
> Der "magische" Schlüssel dürfte wohl [mm](n+1)!=n!*(n+1)[/mm]
> sein, aber ich sehe nicht, wie aus [mm](n-k+1)\*(n-k)!\*k![/mm] dann
> folgt [mm](n-k+1)\*k![/mm]
n-k+1 ist doch der nachfolger von n-k also ist (n-k)!*( (n-k)+1)=(n-k+1)!
entsprechend im anderen nenner (k-1)!*k=(k-1)!*((k-1)+1)=k!
gruss leduart dir die letzten paar glieder von (n-k)! hinzuschreiben häättest du ja mal können
dann steht da 1*2*....*(n-k-2)*(n-k-1)*(n-k) *(n-k+1) du solltest sehen was das ist.
man kann ja auch mal für n und k Zahlen ausprobieren, wenn man was nicht durchschaut as etwa n=4,k=2 und damit experimentieren. auf ne formel starren hilft nie, zahlen einsetzen ist kein Beweis, hilft aber oft mal dei beweisidee zu sehen!
Gruss leduart
>
> [mm]{n+1 \choose k}={n \choose k}+{n \choose k-1}=[/mm]
>
> [mm]=\bruch{n!}{(n-k)!k!}+\bruch{n!}{(n-(k-1))!(k-1)!}[/mm]
>
> [mm]=\bruch{n!}{(n-k)!k!}+\bruch{n!}{(n-k+1)!(k-1)!}[/mm]
>
> [mm]=\bruch{n!(n-k+1)}{(n-k+1)(n-k)!k!}+\bruch{n!k}{(n-k+1)!(k-1)!k}[/mm]
> Erweitern
>
> > erweitern mit dem Ziel von gleichen Nennern. im ersten
> > fehlt zu (n-k+1) Fakultät (n-k+1) das bedeutet unten Def
> > der Fakultat (n+1)!=n!*(n+1)
> > im 2 ten Bruch aus (k-1)! k! erzeugen
>
> [mm]=\bruch{n!(n-k+1)}{(n-k+1)k!}+\bruch{n!k}{(n-k+1)!k!}[/mm]
> Definition der Fakultät
>
> [mm]=\bruch{n!(n-k+1)+n!k}{(n-k+1)k!}[/mm] Zusammenfassen der
> Brüche
>
> [mm]=\bruch{n!(n-k+1+k)}{(n-k+1)!k!}[/mm] Herausheben
>
> [mm]=\bruch{n!(n+1)}{(n+1-k)!k!}[/mm] Addieren
>
> [mm]=\bruch{(n+1)!}{(n+1-k)!k!}[/mm] Definition der Fakultät
>
>
> Hoffe Du erkennst mein Problem...
>
> Vielen Dank
> &
> Gruß
>
> el_grecco
>
|
|
|
|
