somme binomiali

[Simo_the_wolf]

Dimostrare la seguente identità (che dovrebbe essere famosa):

$ \displaystyle \sum_{i=0}^n \binom ni ^2 = \binom {2n}n $

Ora provate a fare questa:

$ \displaystyle \sum_{i\in N} \binom ai \binom b{i+k} = \binom {a+b}{a+k} $

Enjoy

StheW

P.S.: ricordate che $ \binom nk=0 $ se $ k<0 $ o $ k>n $

[what]

Soluzione poco algebrica e molto combinatorica (come si dice? ):
Primo punto: dobbiamo contare i sottoinsiemi di n elementi scelti fra 2n. Allora partizioniamo l'insieme di 2n in due insiemi (A e B) disgiunti, ciascuno con n elementi. Scegliere n elementi fra 2n equivale a sceglierne 0 da A e n da B, oppure 1 da A e n-1 da B, oppure 2 da A e n-2 da B, ecc. In formule

$ \displaystyle \binom{2n}n=\sum_{i=0}^n \binom n i \binom n {n-i}=\sum_{i=0}^n {\binom n i}^2 $

dove nell'ultimo passaggio ho usato $ \binom ni =\binom n{n-i} $.

Il secondo punto si fa in modo simile: ho il mio grande insieme di a+b elementi (tra cui devo prenderne a+k) che divido due insiemi disgiunti, A e B (|A|=a, |B|=b). Con un ragionamento simile a prima, dico che

$ \displaystyle \binom{a+b}{a+k}=\sum \binom b{i+k} \binom a{a+k-(i+k)}= \sum \binom b{i+k} \binom ai $

Ciao!