Sommatoria con binomiale

[luca95]

Dimostrare che per ogni n maggiore di 1 vale

$ \sum_{k=1}^n \binom{n}{k} k=n^3-3n^2+4n $

[Lasker]

Non mi sembra tanto vero , forse intendevi $\sum_{k=1}^n {n\choose k}k=n\cdot 2^{n-1}$?

[luca95]

Hai ragione , la formula vale solo fino ad $ n=4 $, poi cominciano a comparire altri addendi che non avevo considerato... La formula che dici te come si dimostra?

[Lasker]

Un modo stupido di farlo è considerare l'identità del teorema binomiale
$$(1+x)^n=\sum_{k=0}^n {n\choose k}x^k$$
Derivare rispetto ad $x$ da tutte e due le parti, usando la regola per la derivazione della funzione composta al LHS
$$n\cdot(1+x)^{n-1}=\frac{d\sum_{k=0}^n {n\choose k}x^k}{dx}=\sum_{k=0}^n \frac{d{n\choose k}x^k}{dx}=\sum_{k=0}^n k{n\choose k}x^{k-1}=\sum_{k=1}^n k{n\choose k}x^{k-1}$$
Valutando in $x=1$ viene proprio
$$n\cdot 2^{n-1}=\sum_{k=1}^n k{n\choose k}$$

Un modo un po' più carino (ma più difficile da spiegare) sarebbe invece notare che entrambi i membri dell'uguaglianza sono il numero di possibili squadre (scelte da un insieme di $n$ persone) con un capitano scelto all'interno della squadra (questa tecnica dimostrativa, nel caso non la conoscessi, si chiama "double counting", e questa somma è proprio uno degli esempi più classici della sua applicazione )

[luca95]

Grazie mille! Sei stato chiarissimo

[<enigma>]

Più semplicemente (supponendo $n$ pari, dispari si fa uguale) accoppio l'addendo $k$-esimo con l'$(n-k)$-esimo, e poiché $\displaystyle k\binom{n}{k}+(n-k)\binom{n}{n-k}=n\binom{n}{k}$ la somma è uguale a $\displaystyle n \sum_{k=1}^{n/2}\binom{n}{k}=n2^{n-1}$.

[nic.h.97]

Con il double counting si procede in questo modo:
1)Scegliamo un gruppo di $ k $ persone in un insieme di $ n $ persone ; tra queste $ k $ scegliamo il capitano in $ k $ modi.
2)Scegliamo il capitano dall'insieme di $ n $ persone e per tutte quelle rimanenti scegliamo se metterlo o meno nel gruppo . $ n*2^{n-1} $
.... 1) e 2) coincidono