| 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) |
|
