Vollst. Ind. / binom. Lehrsatz < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:02 Mi 16.11.2005 | | Autor: | chrisv |
Hallo, Forum!
Ich habe folgende Aufgabe auf meinem Uebungszettel:
[mm] \sum_{j=1}^{n} (j+1) {n \choose j} = 2^{n-1}(n+2)-1 [/mm].
Zu beweisen durch Induktion ueber [mm] n \in \IN [/mm].
Als Hilfestellung ist [mm] \sum_{j=0}^{n} {n \choose j} = 2^n[/mm] gegeben.
Als Hilfe habe ich mir definiert:
[mm] S_{n} = \sum_{j=1}^{n} (j+1) {n \choose j} [/mm]
[mm] T_{n} = \sum_{j=0}^{n} {n \choose j} [/mm]
Ich habe einen Ansatz aber komme damit auf keinen "gruenen Zweig".
Fuer [mm]n=1[/mm] und [mm]n=2[/mm] habe ich es ueberprueft.
Fuer den Schritt von n auf n+1 gilt:
[mm] S_{n+1} = \sum_{j=1}^{n+1} (j+1) { n+1 \choose j} = 2^n (n+2+1)-1 [/mm]
Ich spalte vom rechten Term die Differenz zwischen n+1 und n ab und setze [mm]S_{n}[/mm] als
Induktionsvorraussetzung ein.
[mm] S_{n+1} = S_{n} + 2^n(n+2) - n2 ^{n-1}[/mm]
Nun ersetze ich [mm]2^n[/mm] durch [mm] T_{n} [/mm] und versuche weiter umzuformen,
komme jedoch nicht auf einen Term mit dem ich [mm]S_{n+1 }[/mm] bilden kann.
Ist dieser Ansatz ueberhaupt brauchbar?
Gruss, Christoph
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hi, Chrisv,
hast Du's schon mal so rum versucht?
> [mm]\sum_{j=1}^{n} (j+1) {n \choose j} = 2^{n-1}(n+2)-1 [/mm].
[mm] \sum_{j=1}^{n} (j+1)*\vektor{n \\ j} [/mm] = [mm] \summe_{i=1}^{n}j*\vektor{n \\ j} [/mm] + [mm] \summe_{i=1}^{n}\vektor{n \\ j}
[/mm]
Da mit Hilfe Deiner Vorgabe [mm] \summe_{i=1}^{n}\vektor{n \\ j} [/mm] = [mm] 2^{n} [/mm] - 1 ist, musst Du nur noch zeigen, dass
[mm] \summe_{i=1}^{n}j*\vektor{n \\ j} [/mm] = [mm] 2^{n-1}*n [/mm] ist.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:54 Do 17.11.2005 | | Autor: | chrisv |
Danke, Zwerglein!
So hatte ich es auch schon probiert, hatte dann aber keine Idee wie ich das [mm]j[/mm] aus der Summe bekomme.
Das habe ich jetzt mit der binomischen Extraktionsregel gemacht. Aber am Ende komm ich wieder nicht so recht weiter.
Behauptung:
[mm] \sum_{j=1}^{n} (j+1) { n \choose j} = 2^{n-1}n [/mm]
Die Zeige ich dann wieder mit vollst. Induktion.
Fuer [mm]n = 1[/mm]. Richtig
Gelte die Beh. fuer ein festes [mm] n \in \IN[/mm] so auch fuer [mm]n+1[/mm].
Fuer [mm] n+1[/mm]:
[mm] \sum_{j=1}^{n+1} j {n+1 \choose j} &=& 2^{n}(n+1) [/mm]
Dann setze ich [mm] 2^n = \sum_{j=0}^{n} {n \choose j}[/mm] ein.
[mm]
\begin{matrix}
\sum_{j=1}^{n+1} j {n+1 \choose j} &=& 2^{n}(n+1)\\
\ &=& \sum_{j=0}^{n+1} {n \choose j} * (n+1) \\
\end{matrix}
[/mm]
Extraktion fuer die linken Seite und Indexverschiebung auf der rechten Seite.
[mm]
n \sum_{j=1}^{n+1} {n \choose j-1} = (n+1) \sum_{j=1}^{n+1} {n \choose j+1}
[/mm]
Hast du vielleicht noch einen Hinweis?
|
|
|
| |
|
Hi, Chris,
naja: Ich hätte es über die Umformung
[mm] \vektor{n+1 \\ j} [/mm] = [mm] \vektor{n \\ j} [/mm] + [mm] \vektor{n \\ j-1} [/mm] versucht
(mit [mm] \vektor{n \\ j} [/mm] = 0 für j > n)
Bin mir aber nicht sicher, ob's geht!
mfG!
Zwerglein
|
|
|
|
