Mächtigkeit Teilmengen < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es soll mit Induktion bewiesen werden:
Die Mächtigkeit der Menge aller k-elementigen Teilmengen von [mm] $\{1,...,n\}$ [/mm] ist ${n [mm] \choose [/mm] k}.$ |
Hallo,
ich scheitere bei dieser Aufgabe am Ende und bräuchte dringend Hilfe.
Induktionsanfang n=1:
${1 [mm] \choose [/mm] k}=0$ für $k=0;1$
Induktionsschritt: $n [mm] \to [/mm] n+1$
Induktionsvoraussetzung: Für ein $n [mm] \in \IN$ [/mm] gelte: Die Mächtigkeit der Menge aller k-elementigen Teilmengen von [mm] $\{1,...,n\}$ [/mm] ist ${n [mm] \choose [/mm] k}.$
Zu zeigen:
Sei [mm] $M:=\{x_{1},...,x_{n+1}\}$ [/mm] eine (n+1)-elementige Menge und $0 [mm] \le [/mm] k [mm] \le [/mm] n+1$. Zu zeigen ist, dass M ${n+1 [mm] \choose [/mm] k}$ verschiedene k-elementige Teilmengen besitzt.
Dann folgt:
Für k=0 oder k=n+1 ist dies wegen ${n+1 [mm] \choose [/mm] 0}={n+1 [mm] \choose [/mm] n+1}=1$ richtig.
Sei also $1 [mm] \le [/mm] k [mm] \le [/mm] n$ dann ${n [mm] \choose [/mm] k}+{n+1 [mm] \choose [/mm] k}=$ ???
Vielen Dank.
Gruß
el_grecco
|
|
| |
|
Huhu el_grecco,
$ [mm] M:=\{x_{1},...,x_{n+1}\} [/mm] $
Der Ansatz ist schonmal gut, nun unterscheide die k-Elementigen Teilmengen mal in solche, die [mm] $x_{n+1}$ [/mm] enthalten und solche, die es nicht tun.
Die die es nicht tun, sind offensichtlich auch die k-Elementigen Teilmengen von [mm] $\{x_{1},...,x_{n}\}$.
[/mm]
Die, die [mm] $x_{n+1}$ [/mm] enthalten, kannst du offensichtlich Schreiben als k-1-Elementige Teilmenge von [mm] $\{x_{1},...,x_{n}\}$ [/mm] vereinigt mit [mm] $\{x_{n+1}\}$
[/mm]
Beide Anzahlen kannst du also offensichtlich nach IV wie berechnen?
MFG,
Gono.
|
|
|
| |
|
Vielen Dank für die rasche Reaktion, Gono. 
Meinst Du das so?
Also besitzt M ${n [mm] \choose [/mm] k-1}+{n [mm] \choose [/mm] k}={n+1 [mm] \choose [/mm] k}$ verschiedene k-elementige Teilmengen, was zu zeigen war.
> Die, die [mm]x_{n+1}[/mm] enthalten, kannst du offensichtlich
> Schreiben als k-1-Elementige Teilmenge von
> [mm]\{x_{1},...,x_{n}\}[/mm] vereinigt mit [mm]\{x_{n+1}\}[/mm]
Was mir leider auch noch nicht einleuchtet ist, warum man hier von einer k-1-elementigen Teilmenge spricht. Was ist der Hintergedanke für dieses k-1 ?
Vielen Dank.
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:19 So 12.12.2010 | | Autor: | Marcel |
Hallo el-grecco,
> Vielen Dank für die rasche Reaktion, Gono.
>
> Meinst Du das so?
>
> Also besitzt M [mm]{n \choose k-1}+{n \choose k}={n+1 \choose k}[/mm]
> verschiedene k-elementige Teilmengen, was zu zeigen war.
>
> > Die, die [mm]x_{n+1}[/mm] enthalten, kannst du offensichtlich
> > Schreiben als k-1-Elementige Teilmenge von
> > [mm]\{x_{1},...,x_{n}\}[/mm] vereinigt mit [mm]\{x_{n+1}\}[/mm]
>
> Was mir leider auch noch nicht einleuchtet ist, warum man
> hier von einer k-1-elementigen Teilmenge spricht. Was ist
> der Hintergedanke für dieses k-1 ?
ohne, dass ich jetzt da wirklich mitgedacht habe (man kann den Beweis übrigens auch mithilfe surjektiver oder injektiver Abbildungen führen):
Soweit ich das mitbekommen habe, wird hier eine "kleine Variante" der Induktion benutzt:
Normalerweise sagt man bei einem Induktionsbeweis, dass im Induktionsschritt aus der Richtigkeit der Aussage [mm] $A(n)\,$ [/mm] die des darauffolgenden Schrittes [mm] $A(n+1)\,$ [/mm] zu zeigen ist.
Bei der hier vorgestellten Variante braucht man beim Induktionsbeweis nicht nur die Richtigkeit von [mm] $A(n)\,,$ [/mm] um [mm] $A(n+1)\,$ [/mm] zu beweisen, sondern auch die von [mm] $A(n-1)\,.$
[/mm]
Genauer gilt:
Neben der üblichen Induktion für eine Aussage:
1.) [mm] $A(n_0)$ [/mm] wird als richtig erkannt
2.) Setzt man für ein $n [mm] \ge n_0$ [/mm] nun [mm] $A(n)\,$ [/mm] voraus, so kann man die Richtigkeit von [mm] $A(n+1)\,$ [/mm] zeigen
(woraus dann folgt, dass [mm] $A(n)\,$ [/mm] für alle natürlichen $n [mm] \ge n_0$ [/mm] gilt)
gibt es auch noch diese Variante für eine vollständige Induktion:
1.) [mm] $A(n_0)$ [/mm] wird als richtig erkannt
2.) Setzt man für ein $n [mm] \ge n_0$ [/mm] voraus, dass [mm] $A(k)\,$ [/mm] für alle [mm] $k=n_0, n_0+1,\ldots,\;n$ [/mm] gilt (kurz: für alle [mm] $k\,$ [/mm] zwischen [mm] $n_0$ [/mm] und [mm] $n\,,$ [/mm] einschließlich der eingrenzenden Zahlen [mm] $n_0$ [/mm] und [mm] $n\,$), [/mm] so folgt die Richtigkeit von [mm] $A(n+1)\,$
[/mm]
Dass die zweite Variante bei Dir benutzt wird (werden sollte), erkennst Du, weil Du im Induktionsschritt für [mm] $n+1\,$ [/mm] nicht nur die entsprechende Formel für das direkt vorhergehende [mm] $n\,$ [/mm] benötigst, sondern auch die von dem [mm] $\tilde{n}=n-1\,,$ [/mm] dass halt "2 Schritte" vor dem [mm] $n+1\,$ [/mm] kam [mm] ($n-1=(n+1)-2\,$). [/mm] Das liegt natürlich an der Rekursionsformel für die Binomialkoeffizienten, wo man halt "2 Vorgänger" benötigt.
Besten Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:28 So 12.12.2010 | | Autor: | el_grecco |
Hallo Marcel,
vielen Dank für Deine Ausführungen. Die Frage nach der (k-1)-elementigen Teilmenge wurde leider damit noch nicht geklärt bzw. ich verstehe es immer noch nicht. Ich habe den status deshalb auf "Frage offen" gesetzt.
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:28 Mi 15.12.2010 | | Autor: | Marcel |
Man siehe Gonos Mitteilung unten!!
|
|
|
| |
|
Huhu,
> Was mir leider auch noch nicht einleuchtet ist, warum man
> hier von einer k-1-elementigen Teilmenge spricht. Was ist
> der Hintergedanke für dieses k-1 ?
naja, wenn wir die k-Elementigen Teilmengen die [mm] $x_{n+1}$ [/mm] enthalten als
$A' [mm] \cup \{x_{n+1}\}$ [/mm] schreiben wollen, muss A' ja k-1 Elemente enthalten, damit $A = A' [mm] \cup \{x_{n+1}\}$ [/mm] k-Elementige Teilmenge ist.
Und ich muss Marcel widersprechen, du benötigst hier nur die Gültigkeit der Aussage für n, NICHT für n-1
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:14 So 12.12.2010 | | Autor: | el_grecco |
1000 Dank für die sehr sehr gute Erklärung, Gono! ![[anbet]](/images/smileys/anbet.gif "[anbet]")
Einen guten Start in die neue Woche!
&
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:27 Mi 15.12.2010 | | Autor: | Marcel |
Hallo,
> Huhu,
>
> > Was mir leider auch noch nicht einleuchtet ist, warum man
> > hier von einer k-1-elementigen Teilmenge spricht. Was ist
> > der Hintergedanke für dieses k-1 ?
>
> naja, wenn wir die k-Elementigen Teilmengen die [mm]x_{n+1}[/mm]
> enthalten als
>
> [mm]A' \cup \{x_{n+1}\}[/mm] schreiben wollen, muss A' ja k-1
> Elemente enthalten, damit [mm]A = A' \cup \{x_{n+1}\}[/mm]
> k-Elementige Teilmenge ist.
>
> Und ich muss Marcel widersprechen, du benötigst hier nur
> die Gültigkeit der Aussage für n, NICHT für n-1
ja stimmt, da hätte ich genauer lesen müssen. Danke für die Richtigstellung (dennoch sollte man die "alternative Induktionsformulierung" auch mal im Hinterkopf behalten, auch, wenn sie hier nicht wirklich zum Einsatz kommt oder benötigt wird).
Beste Grüße,
Marcel
|
|
|
|
