2 Aufgaben, vollst. Induktion < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:18 Do 21.07.2005 | | Autor: | olv |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
ich habe ein Problem mit zwei Aufgaben.
1. Sei p [mm] \in \IN [/mm] fest gewählt. Zeigen Sie, daß für alle q [mm] \in \IN [/mm] mit q [mm] \ge [/mm] p gilt
(1) [mm] \summe_{n=p}^{q} \vektor{n \\ p} [/mm] = [mm] \vektor{q+1 \\ p+1}.
[/mm]
Folgern Sie aus (1) die Gültigkeit von
(2) [mm] \summe_{k=0}^{n} \vektor{n+k \\ k} [/mm] = [mm] \bruch{1}{2}\vektor{2n+2 \\ n+1}
[/mm]
für alle natürlichen Zahlen n.
Den Beweis für (1) habe ich mit vollständiger Induktion leicht hinbekommen, aber wie folgere ich (2) aus (1) ?
2. Sei n [mm] \in \IN [/mm] beliebig. Zeigen Sie:
[mm] \summe_{k=0}^{n} (\vektor{n \\ k})^2 [/mm] = [mm] \vektor{2n \\ n}.
[/mm]
Egal wie ich die vollständige Induktion probiere, ich komme zu keinem vernünftigen Ergebnis (auf der linken Seite bleibt immer zuviel übrig).
Ich hoffe mir kann hier jemand helfen. Vielen Dank im Voraus.
|
|
| |
|
Hallo olv,
Hier die Lösung für Punkt 1:
[mm] $\frac{1}{2}*\vektor{2n+2 \\ n+1} [/mm] =$ (p=n, q=2n+1)
[mm] $\frac{1}{2}*\summe_{k=n}^{2n+1} \vektor{k \\ n} [/mm] =$ (Indexschift)
[mm] $\frac{1}{2}*\summe_{k=0}^{n+1} \vektor{n+k \\ n} [/mm] =$ (*)
[mm] $\frac{1}{2}*\summe_{k=0}^{n+1} \vektor{n+k \\ k} [/mm] =$
[mm] $\frac{1}{2}*(\summe_{k=0}^{n} \ldots [/mm] + [mm] \vektor{2n+1 \\ n+1}) [/mm] =$ (**)
[mm] $\frac{1}{2}*(\summe_{k=0}^{n} \ldots [/mm] + [mm] \summe_{k=0}^{n} \ldots [/mm] )=$
[mm] $\summe_{k=0}^{n} \ldots$
[/mm]
Für (*) habe ich benutzt dass [mm] $\vektor{n \\k } [/mm] = [mm] \vektor{n \\ n-k}$. [/mm] Und für (**) habe ich die Formel
[mm] $\summe_{k=0}^n \vektor{ n+k \\ k}$ [/mm] = [mm] $\vektor{ 2n+1 \\ n+1 }$
[/mm]
benutzt, die wohl so oder so ähnlich in Deinem Skriptum steht, wenn ihr euch mit Kombinatorik beschäftigt.
Liebe Grüße,
Holy Diver
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:26 Sa 23.07.2005 | | Autor: | SEcki |
> [mm]\summe_{k=0}^{n} (\vektor{n \\ k})^2[/mm] = [mm]\vektor{2n \\ n}.[/mm]
Das geht auch mit vollständiger Induktion - aber ich erinnere mich egrade nicht dran. Hier ein alternativer Beweis durch doppeltes Abzählen (bin quasi stolz daruaf, weil ich das auf meinem zweiten Ü-Blatt in Anna drauf war, und ich eine imo sehr schöne Lösung gefundne habe  ):
Es seien 2n Kugeln gegeben, n rote und n weiße. auf wieviele Weisen lassen sich n Kugeln aus den 2n auswählen ohne auf die Reihenfolge zu achten? dazu zweio Methoden das zu brechnen:
1. [mm]\vektor{2n \\ n}[/mm]: Klar.
2. Man fixiere ein k. Dann kann man sich überlegen: man nimmt erstmal k rote, und danach n-k weiße heraus. Also liefert [m]\vektor{n \\ k}\vektor{n\\n-k}[/m] die anzahl der Möglichkeiten erst k rote und dann n-k weiße, also insgesamt immer n Kugeln, zu separieren. Wenn man jetzt über alle passendne k's summiert, erhält man wieder die Anzahl aller Möglichkeiten, n Kugeln auszuwählen (da dies ja disjunkt in Familien zerfällt, bei denne die Anzahl der roten konstant ist), also [m]\summe_{k=0}^{n} \vektor{n \\ k}\vektor{n \\ n-k}=\summe_{k=0}^{n} (\vektor{n \\ k})^2[/m].
Da 1.=2. ist folgt alles.
SEcki
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:52 Sa 23.07.2005 | | Autor: | olv |
Vielen,vielen Dank.
|
|
|
|
