Binomiali

[FeddyStra]

Dimostrare le seguenti identità:

1) $ \displaystyle\sum_{i=0}^{n}\binom{n}{i}\binom{kn}{i}=\binom{(k+1)n}{n} $

2) $ \displaystyle\sum_{i=0}^{n}\binom{n}{i}/\binom{kn}{i}=\frac{kn+1}{(k-1)n+1} $

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

[karl]

Risolvo il primo esercizio.Poniamo:
$ \displaystyle (1+x)^n(1+x)^{kn}=(1+x)^{n+kn} $
Sviluppando i binomiali abbiamo:
$ \displaystyle \sum_{r=0}^n\binom{n}{r}x^r\cdot\sum_{s=0}^{kn}\binom{kn}{s}x^s=\sum_{t=0}^{n+kn}\binom{kn+n}{t}x^t $
Questa identità ,in quanto tale,deve essere verificata per qualunque valore di x.
E ciò è possibile sse sono uguali i coefficienti delle potenze di x presenti nei
due membri con eguale esponente.In particolare per la potenza
$ \displaystyle x^n $ deve essere:
$ \displaystyle\sum_{r+s=n}[\binom{n}{r}\binom{kn}{s}]=\binom{kn+n}{n} $
dove la sommatoria a primo membro è estesa a tutti i
valori,interi non negativi,di r e di s tali che r+s=n
Esprimendo in funzione di s, risulta:
$ \displaystyle \sum_{s=0}^n\binom{n}{n-s}\binom{kn}{s}=\binom{kn+n}{n} $
ma $ \displaystyle \binom{n}{n-s}=\binom{n}{s} $ e dunque si ha:
$ \displaystyle \sum_{s=0}^n\binom{n}{s}\binom{kn}{s}=\binom{kn+n}{n} $
che è la tesi.

[FeddyStra]

Bene.
C'è anche la versione combinatorica. Suppponiamo di avere $ (k+1)n $ palline e di volerne prendere $ n $. Questo lo posso fare in $ \displaystyle\binom{(k+1)n}n $ modi.
Lo posso però fare anche in questo modo. Divido le palline in due gruppi: $ A $ contiene $ kn $ palline, $ B $ ne contiene $ n $. Ora prendo $ i $ palline da $ A $ e $ n-i $ da $ B $. Questo lo posso fare in $ \displaystyle\binom{kn}i\binom{n}{n-i}=\binom{kn}i\binom{n}i $ modi. Se faccio variare $ i $ tra $ 0 $ e $ n $ in questa maniera conto tutti i modi possibili.
Dunque $ \displaystyle\sum_{i=0}^n\binom{kn}i\binom{n}i=\binom{(k+1)n}n $.

[kn]

Si può anche notare che $ \displaystyle~\sum_{i=0}^{n}\binom{n}{i}\binom{kn}{i} $ è il coefficiente del termine di grado n del polinomio (in t) $ \displaystyle~\sum_{i=0}^{n}\binom{n}{i}t^{n-i}\sum_{j=0}^{kn}\binom{kn}{j}t^j=(t+1)^{kn}\sum_{i=0}^{n}\binom{n}{i}t^{n-i} $$ \displaystyle~=(t+1)^{kn}(t+1)^n=(t+1)^{(k+1)n} $.
Ma il coefficiente del termine di grado n è proprio $ \displaystyle~\binom{(k+1)n}{n} $. (Ok sostanzialmente è la soluzione di karl... )

3) $ \displaystyle~\sum_{i=0}^{n}(-1)^i\binom{n}{i}\binom{n+i}{i}=\sum_{i=0}^{n}(-1)^i\binom{n}{i}\binom{n+i}{n} $ e di nuovo notiamo che è il coefficiente del termine di grado n del polinomio $ \displaystyle~\sum_{i=0}^{n}(-1)^i\binom{n}{i}\sum_{j=0}^{n+i}\binom{n+i}{j}t^j=\sum_{i=0}^{n}(-1)^i\binom{n}{i}(t+1)^{n+i} $$ \displaystyle~=(t+1)^n\sum_{i=0}^n(-t-1)^i=(t+1)^n(-t)^n $. $ \displaystyle~(-t)^n $ impone che per avere il termine di grado n dobbiamo prendere quello di grado 0 di $ \displaystyle~(t+1)^n $, cioè 1. Esso è quindi $ \displaystyle~(-t)^n $, da cui il coefficiente voluto che rispecchia la tesi.

[FeddyStra]

Purtroppo per questa (la 3) non sono in possesso di una dimostrazione con gli insiemi.
Ora resta solo più la 2... che non ho fatto...

[kn]

Ora resta solo più la 2... che non ho fatto...

Hintone

[FeddyStra]

Hintone

Veramente bello!
PS: il tuo nome oltretutto è molto in tema con il problema...

[kn]

Hintone

PS: il tuo nome oltretutto è molto in tema con il problema...

In effetti con tutti questi "kn" mi sono sentito come chiamato in causa