Dimostrare:
$
\displaystyle
\sum_{k=0}^n \binom{n}{k}^2\binom{k}{n-j} = \binom{n}{j}\binom{n+j}{j}
$
e
$
\displaystyle
\sum_{k=0}^{2n} (-1)^k\binom{2n}{k}\binom{n+k}{k}^2 = \binom{2n}{n}
$
Somme con binomiali al quadrato
Ma son belli e divertenti questi problemi di interpretazione!
Scrivendo $ i=n-j $, riscrivo il primo problema nel modo più comodo:
$ \displaystyle \sum_{k=0}^n {n \choose k}^2 {k \choose i} = {n \choose i}{2n-i \choose n} $
Dobbiamo organizzare un gioco tra n bambini. Per far questo li dobbiamo dividere in due squadre con lo stesso numero di bambini (ma un bambino può anche essere in entrambe le squadre o in nessuna!). Inoltre, nella prima squadra devo eleggere esattamente un numero fissato i di capitani.
Posso operare in due modi.
Primo: conto i modi separatamente secondo il numero di bambini in ciascuna squadra. Se questo numero è k, allora la prima squadra la scelgo in $ n \choose k $ modi, la seconda in $ n \choose k $ modi, e i capitani della prima squadra in $ k \choose i $ modi, che ci da la LHS.
Oppure: prima scelgo i capitani, in $ n \choose i $ modi. Poi scrivo su un foglio prima tutti i nomi dei bambini, poi di nuovo i nomi di tutti i bambini che non sono stati scelti come capitani. Da questo elenco scelgo n nomi in $ 2n-i \choose n $ modi. Di tutti i nomi scelti nella prima parte dell'elenco, mettiamo siano k, faccio la seconda squadra. Per fare la prima squadra, invece, metto insieme i capitani già scelti a tutti i bambini non scelti nella seconda parte dell'elenco, che sono $ (n-i)-(n-k) = k-i $, quindi anche la prima squadra ha in totale k giocatori.
Scrivendo $ i=n-j $, riscrivo il primo problema nel modo più comodo:
$ \displaystyle \sum_{k=0}^n {n \choose k}^2 {k \choose i} = {n \choose i}{2n-i \choose n} $
Dobbiamo organizzare un gioco tra n bambini. Per far questo li dobbiamo dividere in due squadre con lo stesso numero di bambini (ma un bambino può anche essere in entrambe le squadre o in nessuna!). Inoltre, nella prima squadra devo eleggere esattamente un numero fissato i di capitani.
Posso operare in due modi.
Primo: conto i modi separatamente secondo il numero di bambini in ciascuna squadra. Se questo numero è k, allora la prima squadra la scelgo in $ n \choose k $ modi, la seconda in $ n \choose k $ modi, e i capitani della prima squadra in $ k \choose i $ modi, che ci da la LHS.
Oppure: prima scelgo i capitani, in $ n \choose i $ modi. Poi scrivo su un foglio prima tutti i nomi dei bambini, poi di nuovo i nomi di tutti i bambini che non sono stati scelti come capitani. Da questo elenco scelgo n nomi in $ 2n-i \choose n $ modi. Di tutti i nomi scelti nella prima parte dell'elenco, mettiamo siano k, faccio la seconda squadra. Per fare la prima squadra, invece, metto insieme i capitani già scelti a tutti i bambini non scelti nella seconda parte dell'elenco, che sono $ (n-i)-(n-k) = k-i $, quindi anche la prima squadra ha in totale k giocatori.