Autor |
Beitrag |
AquaMage (Aquamage)
| Veröffentlicht am Sonntag, den 04. November, 2001 - 12:59: |
|
Hallo! Ich soll folgendes mit vollständiger Induktion beweisen: Summe k=1 bis n (n über k)*k=2^(n-1)*n Hab keine Ahnung, wie ich das machen soll. |
Hans (Birdsong)
| Veröffentlicht am Sonntag, den 04. November, 2001 - 14:38: |
|
AquaMage: Die fragliche Summe heisse S(n). Dann ist S(n+1) = sum[k=1..(n+1)]k*binom(n+1,k) = sum[k=0..n](k+1)*binom(n+1,k+1). Beachte nun, dass (1) binom(n+1,k+1) = binom(n,k) + binom(n,k+1). Setzt man dies ein und benutzt die bekannte Formel sum[k=0..n]binom(n,k) = 2^n, so erhaelt man die Rekursionsformel S(n+1) = 2*S(n) + 2^n womit sich der Induktionsschluss leicht ergibt. Einfacher geht's ohne Induktion: Differenziere die Gleichung (binomischer Satz !) (1+x)^n = sum[k=0..n]x^k beiderseits nach x und setze x=1. Man kann auch statt (1) die Gleichung binom(n+1,k+1) = [(n+1)/(k+1)]*binom(n,k) benutzen und erhaelt direkt S(n+1) = (n+1)*sum[k=0..n]binom(n,k) = (n+1)*2^n. mfg Hans |
sand
| Veröffentlicht am Montag, den 05. November, 2001 - 21:12: |
|
Oder guck mal unter dem Thema: Induktion ähnlich wie beim binomischen satz!? (auch unter Mathe für Informatiker) |
|