indentità con prodotto di binomiali e cubi

[salva90]

Provare la seguente identità:

$ \displaystyle\sum_{k=1}^{n}\binom{n}{k}k^3=n^2(n+3)2^{n-3} $


buon lavoro by salva

[darkcrystal]

Riscriviamo:
$ \displaystyle \sum_{k=1}^{n} \frac{n(n-1)!}{k!(n-k)!}k^3 =n\sum_{k=1}^{n} \frac{(n-1)!}{(k-1)!(n-k)!}k^2 = n\sum_{k=0}^{n-1} {n-1 \choose k}(k+1)^2 $ che vogliamo dimostrare essere $ n^2(n+3)2^{n-3} $
Semplificando un fattore n resta da dimostrare che $ \displaystyle \sum_{k=0}^{n-1} {n-1 \choose k}(k+1)^2=n(n+3)2^{n-3} $. Ma la prima somma si spezza in tre somme abbastanza note: $ \displaystyle \sum_{k=0}^{n-1} {n-1 \choose k}(k^2+2k+1) $, somme che fanno $ 2^{n-3} \cdot (n(n-1)+4(n-1)+4)=2^{n-3} n(n+3) $
Giacchè mi trovo, potrei anche dimostrarle... l'ultima mi pare sufficientemente nota, quindi parliamo di una delle altre due: $ \displaystyle \sum_{k=0}^{n-1} {n-1 \choose k}k= $$ \displaystyle \sum_{k=1}^{n-1} \frac{(n-1)(n-2)!}{k!(n-1-k)!}k=(n-1)\sum_{k=0}^{n-2} {n-2 \choose k-1} $$ =(n-1)2^{n-2} $
Vabbè, penso abbiate capito come funziona il trucco, no?

Ciao!

[edriv]

Oppure, cercando di capire cosa vuole dire quella sommatoria:
Abbiamo n persone, e vogliamo formare una squadra (con almeno una persona), e in questa squadra scegliere il capo, il vicecapo o il portaborse. Per mancanza di fondi potrebbe accadere che il capo si porti la borsa da solo, o più in generale, che i ruoli coincidono. In quanti modi possiamo farlo?

Modo "dalla parte della mano sinistra".
Scelgo prima quanti membri avrà la squadra, diciamo k. Poi scelgo k persone e, tra queste, il capo, il vicecapo, e il portaborse.

Modo "dalla parte della mano sinistra".
Intanto scelgo il capo, vicecapo, e portaborse. Poi, a seconda delle coincidenze:
- ho scelto in totale una persona. Allora per ciascuna delle rimanenti n-1, decido se metterla nella squadra
- ho scelgo due persone, sono in dubbio solo sulle altre n-2
- ho scelto tre persone, la squadra la completerò con le altre n-3

[jordan]

x darkcrystal, l'ultimo binomiale con quegli estremanti è n-2 su k giusto?

[Xamog]

Forse sarebbe utile che qualcuno postasse anche la soluzione con le derivate della funzione generatrice.

[EvaristeG]

Ah la forza bruta...
Beh,

1° Fatto:
$ \displaystyle{\sum_{k=0}^n{n\choose k}x^k=(1+x)^n $
e su questo siamo tutti d'accordo.

2° Fatto:
Se $ \displaystyle{f(x)=\sum_{k=0}^n{n\choose k}x^k $ allora
$ \displaystyle{f'(x)=\sum_{k=1}^n{n\choose k}kx^{k-1} $.

3° Fatto:
$ xf'(x)=\displaystyle{\sum_{k=1}^n{n\choose k}kx^k} $

Se dunque concordiamo di indicare con $ \dfrac{d}{dx}f(x) $ la derivata di f, abbiamo il
4° Fatto:
$ \displaystyle{g(x)=\frac{d}{dx}x\cdot\left(\frac{d}{dx}x\cdot\left(\frac{d}{dx}f(x)\right)\right)=\sum_{k=1}^n{n\choose k}k^3x^{k-1}} $
e dunque basta calcolare g(1).

Facciamo il conto:
$ f(x)=(1+x)^n $
$ \dfrac{d}{dx}f(x)=n(1+x)^{n-1} $
$ \dfrac{d}{dx}x(n(1+x)^{n-1})=n(n-1)(1+x)^{n-2}x+n(1+x)^{n-1} $
$ \dfrac{d}{dx}x(n(n-1)(1+x)^{n-2}x+n(1+x)^{n-1})= $$ n(n-1)(n-2)(1+x)^{n-3}x^2+2n(n-1)(1+x)^{n-2}x $$ +n(n-1)(1+x)^{n-2}x+n(1+x)^{n-1} $$ =g(x) $

Ed ora: $ g(1)=n(n-1)(n-2)2^{n-3}+3n(n-1)2^{n-2}+n2^{n-1} $$ =2^{n-3}n(n^2-3n+2+6n-6+4)=2^{n-3}n^2(n+3) $

Rapido, brutto e indolore.