OliForum Matematico

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 $

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.

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 $.

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.

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...

FeddyStra ha scritto:Ora resta solo più la 2... che non ho fatto...

Hintone

kn ha scritto:Hintone

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

FeddyStra ha scritto:

kn ha scritto: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