Binomialkoeffizienten < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Man zeige: Für alle [mm] n\in\IN [/mm] gilt [mm] \vektor{2n \\ n} [/mm] = [mm] \summe_{k=0}^{n} \vektor{n \\ k}^2. [/mm] |
Hallo zusammen...
ich steh grad bezüglich der Rechenengeln für Binomialkoeffizienten ein bissel auf dem Schlauch und hoffe ihr könnt mir helfen.
Das hab ich bisher:
Wir halten k fest und beweisen die Beh. durch vollst. Ind. nach n.
Ind.anfang n=1:
[mm] \vektor{2 \\ 1}=2=\summe_{k=0}^{1} \vektor{n\\ k}^2=1+1
[/mm]
Ind.schluss n -> n+1:
Es gelte die Beh. für ein beliebiges [mm] n\in\IN, [/mm] dann ist
[mm] \vektor{2n+2 \\ n+1} [/mm] = [mm] \summe_{k=0}^{n+1}\vektor{n \\ k}^2 [/mm]
zu bestätigen.
Nun gilt nach Ind.annahme
[mm] \summe_{k=0}^{n+1}\vektor{n \\ k}^2 [/mm] = [mm] \summe_{k=0}^{n}\vektor{n \\ k}^2+\vektor{n+1\\ k}^2
[/mm]
= [mm] \vektor{2n \\ n}+\vektor{n+1\\ k}^2
[/mm]
soo... mein Problem ist jetzt,...
wie zeige ich das
[mm] \vektor{2n+2 \\ n+1} [/mm] = = [mm] \vektor{2n \\ n}+\vektor{n+1\\ k}^2
[/mm]
???
Ich hoffe ihr könnt mir am schluss noch helfen...
lg
tinchen
|
|
| |
|
Hallo Tinchen!
> Ind.schluss n -> n+1:
> Es gelte die Beh. für ein beliebiges [mm]n\in\IN,[/mm] dann ist
> [mm]\vektor{2n+2 \\ n+1}[/mm] = [mm]\summe_{k=0}^{n+1}\vektor{n \\ k}^2[/mm]
> zu bestätigen.
![[notok]](/images/smileys/notok.gif "[notok]") Es gilt zu bestätigen:
[mm] $$\vektor{2n+2 \\ n+1} [/mm] \ = \ [mm] \summe_{k=0}^{n+1}\vektor{n \ \red{+1} \\ k}^2$$
[/mm]
> Nun gilt nach Ind.annahme
> [mm]\summe_{k=0}^{n+1}\vektor{n \\ k}^2[/mm] = [mm]\summe_{k=0}^{n}\vektor{n \\ k}^2+\vektor{n+1\\ k}^2[/mm] = [mm]\vektor{2n \\ n}+\vektor{n+1\\ k}^2[/mm]
Auch hier muss es nun heißen (mit obigen Hinweis):
[mm] $$\summe_{k=0}^{n+1}\vektor{n+1 \\ k}^2 [/mm] \ = \ [mm] \summe_{k=0}^{n}\vektor{n+1 \\ k}^2+\vektor{n+1 \\ n+1}^2 [/mm] \ = \ ...$$
Gruß vom
Roadrunner
|
|
|
| |
|
Ok... jetzt bin ich noch ein wenig mehr verwirrt....
sollte es dann am schluss nicht heissen:
[mm] \summe_{k=0}^{n+1}\vektor{n+1 \\ k}^2 [/mm] = [mm] \summe_{k=0}^{n}\vektor{n+1 \\ k}^2+\vektor{n+1 \\ n+1}^2 [/mm] = ...
bzw. wie wurde aus n+1 über k, plötzlich n+1 über n+1 ????
ich hatte ja vorher festgelegt, das k fest ist....
und am schluss... müsste ich nach wie vor zeigen, dass
[mm] \vektor{2n+2 \\ n+1} [/mm] = [mm] \vektor{2n \\ n}+\vektor{n+1\\ k}^2
[/mm]
was ich nicht schaffe...
hilfe!
|
|
|
| |
|
> Ok... jetzt bin ich noch ein wenig mehr verwirrt....
>
> sollte es dann am schluss nicht heissen:
>
> [mm]\summe_{k=0}^{n+1}\vektor{n+1 \\ k}^2[/mm] =
> [mm]\summe_{k=0}^{n}\vektor{n+1 \\ k}^2+\vektor{n+1 \\ n+1}^2[/mm]
Hallo,
ja.
> ich hatte ja vorher festgelegt, das k fest ist....
??? Was meinst Du damit? k ist halt die Summationsvariable.
>
> und am schluss... müsste ich nach wie vor zeigen, dass
>
> [mm]\vektor{2n+2 \\ n+1}[/mm] = [mm]\vektor{2n \\ n}+\vektor{n+1\\ k}^2[/mm]
Nein. Du mußt zeigen, daß [mm]\vektor{2n+2 \\ n+1}[/mm] = [mm]\summe_{k=0}^{n+1}\vektor{n+1 \\ k}^2[/mm].
Achtung: es ist [mm] \summe_{k=0}^{n}\vektor{n+1 \\ k}^2 \not= \summe_{k=0}^{n}\vektor{n \\ k}^2=\vektor{2n\\n} [/mm] ...
Ich habe die Aufgabe nicht durchgerechnet, aber ich wurde mal so einen Beginn versuchen
[mm]\summe_{k=0}^{n+1}\vektor{n+1 \\ k}^2[/mm]= 1+ [mm]\summe_{k=1}^{n}\vektor{n+1 \\ k}^2[/mm] +1
=1+ [mm]\summe_{k=1}^{n}(\vektor{n \\ k-1}+\vektor{n\\k})^2[/mm] +1
Gruß v. Angela
|
|
|
| |
|
Hallo!
Ich interessiere mich für die Lösung dieser Aufgabe, weil ich sie selbst auch nicht so recht hinbekommen will.
Zu zeigen ist [mm] $\vektor{2n\\n} [/mm] = [mm] \sum_{k=0}^{n}\vektor{n\\k}^{2}$, [/mm] mit Induktion.
Angela hat ja schon folgenden Anfang gemacht, den ich auch wählen würde:
[mm] $\summe_{k=0}^{n+1}\vektor{n+1 \\ k}^2$
[/mm]
$= [mm] 2+\summe_{k=1}^{n}\vektor{n+1 \\ k}^2 [/mm] $
$ =2+ [mm] \summe_{k=1}^{n}\left(\vektor{n \\ k-1}+\vektor{n\\k}\right)^2$ [/mm]
Nun würde es wahrscheinlich mit Ausmultiplizieren weitergehen:
$ =2+ [mm] \summe_{k=1}^{n}\left(\vektor{n \\ k-1}^{2}+2*\vektor{n \\ k-1}*\vektor{n \\ k}+\vektor{n\\k}^{2}\right)$ [/mm]
$ [mm] =2*\vektor{2n\\n} [/mm] + [mm] 2*\summe_{k=1}^{n}\vektor{n \\ k-1}*\vektor{n \\ k}$ [/mm]
Die beiden Quadrate kann man jetzt ja mit der Induktionsvoraussetzung verarzten, aber wie sieht es mit dem mittleren Term aus? Ich glaube, so komme ich nicht zum Ziel...
Wenn man von der anderen Seite losgeht, kommt man auf:
[mm] $\vektor{2*(n+1)\\n+1} [/mm] = [mm] \vektor{2n+2\\n+1} [/mm] = [mm] \frac{(2n+2)!}{(n+1)!*((2n+2)-(n+1))!}$
[/mm]
$= [mm] \frac{(2n+2)*(2n+1)}{(n+1)*(n+1)}*\frac{(2n)!}{n!*n!} [/mm] = [mm] 2*\frac{2n+1}{n+1}*\vektor{2n\\n}$
[/mm]
$= [mm] 2*\left(1 + \frac{n}{n+1}\right)*\vektor{2n\\n}$.
[/mm]
Das würde im Vergleich zu oben nahe legen, dass [mm] $\summe_{k=1}^{n}\vektor{n \\ k-1}*\vektor{n \\ k} [/mm] = [mm] \frac{n}{n+1}*\vektor{2n\\n}$. [/mm] Aber habe ich eine Chance, mit der Induktionsvoraussetzung dazu zu kommen?
Danke für Eure Hilfe!
Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:00 Do 04.03.2010 | | Autor: | abakus |
> Hallo!
>
> Ich interessiere mich für die Lösung dieser Aufgabe, weil
> ich sie selbst auch nicht so recht hinbekommen will.
>
> Zu zeigen ist [mm]\vektor{2n\\n} = \sum_{k=0}^{n}\vektor{n\\k}^{2}[/mm],
> mit Induktion.
> Angela hat ja schon folgenden Anfang gemacht, den ich auch
> wählen würde:
>
>
> [mm]\summe_{k=0}^{n+1}\vektor{n+1 \\ k}^2[/mm]
>
> [mm]= 2+\summe_{k=1}^{n}\vektor{n+1 \\ k}^2[/mm]
>
> [mm]=2+ \summe_{k=1}^{n}\left(\vektor{n \\ k-1}+\vektor{n\\k}\right)^2[/mm]
>
> Nun würde es wahrscheinlich mit Ausmultiplizieren
> weitergehen:
>
> [mm]=2+ \summe_{k=1}^{n}\left(\vektor{n \\ k-1}^{2}+2*\vektor{n \\ k-1}*\vektor{n \\ k}+\vektor{n\\k}^{2}\right)[/mm]
>
> [mm]=2*\vektor{2n\\n} + 2*\summe_{k=1}^{n}\vektor{n \\ k-1}*\vektor{n \\ k}[/mm]
>
> Die beiden Quadrate kann man jetzt ja mit der
> Induktionsvoraussetzung verarzten, aber wie sieht es mit
> dem mittleren Term aus?
Hallo,
[mm] \vektor{n \\ k} [/mm] enthält im Zähler n! und im Nenner k!*(n-k)!.
[mm] \vektor{n \\ k-1} [/mm] enthält im Zähler n! und im Nenner (k-1)! (der Faktor k fehlt also im Vergleich zur Zeile darüber) mal (n-(k-1))! (der Faktor n-k+1 ist also zusätzlich dazugekommen).
Somit kann man [mm] \vektor{n \\ k-1}*\vektor{n \\ k} [/mm] schreiben als [mm] \vektor{n \\ k}^2*\bruch{k}{n-k+1}.
[/mm]
Hilft das vieleicht weiter?
Gruß Abakus
> Ich glaube, so komme ich nicht zum
> Ziel...
>
> Wenn man von der anderen Seite losgeht, kommt man auf:
>
> [mm]\vektor{2*(n+1)\\n+1} = \vektor{2n+2\\n+1} = \frac{(2n+2)!}{(n+1)!*((2n+2)-(n+1))!}[/mm]
>
> [mm]= \frac{(2n+2)*(2n+1)}{(n+1)*(n+1)}*\frac{(2n)!}{n!*n!} = 2*\frac{2n+1}{n+1}*\vektor{2n\\n}[/mm]
>
> [mm]= 2*\left(1 + \frac{n}{n+1}\right)*\vektor{2n\\n}[/mm].
>
> Das würde im Vergleich zu oben nahe legen, dass
> [mm]\summe_{k=1}^{n}\vektor{n \\ k-1}*\vektor{n \\ k} = \frac{n}{n+1}*\vektor{2n\\n}[/mm].
> Aber habe ich eine Chance, mit der Induktionsvoraussetzung
> dazu zu kommen?
>
> Danke für Eure Hilfe!
>
> Grüße,
> Stefan
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 13:33 Do 04.03.2010 | | Autor: | steppenhahn |
Hallo akakus,
danke für deine Antwort!
> [mm]\vektor{n \\ k}[/mm] enthält im Zähler n! und im Nenner
> k!*(n-k)!.
> [mm]\vektor{n \\ k-1}[/mm] enthält im Zähler n! und im Nenner
> (k-1)! (der Faktor k fehlt also im Vergleich zur Zeile
> darüber) mal (n-(k-1))! (der Faktor n-k+1 ist also
> zusätzlich dazugekommen).
> Somit kann man [mm]\vektor{n \\ k-1}*\vektor{n \\ k}[/mm] schreiben
> als [mm]\vektor{n \\ k}^2*\bruch{k}{n-k+1}.[/mm]
> Hilft das
> vieleicht weiter?
Ich befürchte, nein.
Weil dann bekomme ich ja etwas ganz anderes in die Summe, und ich wüsste nicht, wie ich darauf die Induktionsvoraussetzung
[mm] \sum_{k=0}^{n}\vektor{n\\k}^{2} [/mm] = [mm] \vektor{2n\\n}
[/mm]
anwenden könnte...
Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:50 Fr 05.03.2010 | | Autor: | tobit09 |
Hallo zusammen,
per Induktion konnte ich die Aussage leider auch nicht beweisen. Aber mit kombinatorischen Überlegungen lässt sich die behauptete Gleichheit ohne große Rechnung einsehen:
Für beliebige Mengen M und beliebige natürliche Zahlen n sei [mm] $P_n(M)$ [/mm] die Menge der n-elementigen Teilmengen von M.
Seien nun M und N zwei beliebige disjunkte n-elementige Mengen. Dann gilt [mm] $\vektor{2n\\n}=|P_n(M\cup [/mm] N)|$.
Für [mm] $k\in\{0,\ldots,n\}$ [/mm] sei [mm] $A_k$ [/mm] die Menge der n-elementigen Teilmengen von [mm] $M\cup [/mm] N$, die genau k Elemente von M enthalten. Dann ist [mm] $P_n(M\cup [/mm] N)$ die disjunkte Vereinigung der [mm] $A_k$ [/mm] für [mm] $k\in\{0,\ldots,n\}$. [/mm] Somit erhalten wir [mm] $|P_n(M\cup N)|=\sum_{k=0}^n|A_k|$.
[/mm]
Die [mm] $A_k$ [/mm] stehen jeweils kanonisch in Bijektion zu [mm] $P_k(M)\times P_{n-k}(N)$. [/mm] Somit gilt [mm] $|A_k|=|P_k(M)\times P_{n-k}(N)|=|P_k(M)|*|P_{n-k}(N)|=\vektor{n\\k}*\vektor{n\\n-k}=\vektor{n\\k}^2$.
[/mm]
Insgesamt erhalten wir wie gewünscht [mm] $\vektor{2n\\n}=\sum_{k=0}^n\vektor{n\\k}^2$.
[/mm]
Viele Grüße
Tobias
|
|
|
| |
|
Hallo Tobias,
dein Beweis gefällt mir auch sehr gut 
Grüße,
Stefan
|
|
|
|
