Identità con i binomiali

[jordan]

Mostrare che per ogni intero positivo $n$ vale
\[ \sum_{k}\binom{n}{k}\binom{n-1}{k-1}=\binom{2n-1}{n-1} \]

Ps, esistono almeno due soluzioni completamente differenti

[Drago96]

Soluzione combinatorica

Testo nascosto:

Riscrivo come $\displaystyle\sum_k^n\binom n k\binom{n-1}{n-k}=\binom{2n-1}n$
A sinistra è come se avessi due contenitori, uno con $n$ palline e uno con $n-1$ palline, e sto contando in quanti modi posso prenderne $k$ da uno e $n-k$ dall'altro; dato che $k$ assume tutti i valori, sto contando in quanti modi posso prendere $n$ palline da un contenitore con $2n-1$ palline (se penso di unire i due contenitori di prima), che è la parte destra.

Questo "trucco" può essere usato per mostrare, per esempio, $\displaystyle\sum\binom n k^2=\binom{2n}n$

[Ido Bovski]

Generalizzazione. Per ogni $n$, $m$, $j\in\mathbb{N}$
$$\sum_{i=0}^j \binom{n}{j-i}\binom{m}{i}=\binom{n+m}{j}.$$

[auron95]

A me è venuta in mente una dimostrazione con il triangolo di Tartaglia.

Gli $\binom{n-1}{k-1}$ sono i numeri sull'n-esima riga del triangolo.
Gli $\binom{n}{k}$ sono quelli dell'$n+1$-esima meno il primo.
$\binom{2n-1}{n}$ è il terzo vertice del sottotriangolo rovesciato che ha per lato gli $\binom{n}{k}$

Ora mi basta dimostrare che se prendo un sottotriangolo con la punta verso il basso, e considero la riga con $n$ elementi che chiamo $a_0,a_1,\dots,a_{n-1}$ allora la somma
$\displaystyle \sum_{k=0}^{n-1} \binom{n-1}{k}a_k$ è costante qualsiasi riga del sottotriangolo consideri. Infatti se prendo come $a_k$ gli $\binom{n}{k}$ allora la somma che rimane costante nel sottotriangolo è l'LHS se prendo la riga con n elementi, e se considero la riga con solo il vertice in basso corrisponde al RHS.

Lo dimostro per induzione: considero le righe con n e n-1 elementi e dimostro che quella sommatoria è costante:
\begin{array}{ccccccccccc} a_0 && a_1 && a_2 && \dots && a_{n-2} && a_{n-1}\\ & a_0+a_1 && a_1+a_2 && \dots && \dots && a_{n-2}+a_{n-1} & \end{array}

Nella seconda riga la sommatoria diventa
$\displaystyle \sum_{i=0}^{n-2} \binom{n-2}{i}( a_i +a_{i+1}) = a_0\binom{n-2}{0} + a_1\left(\binom{n-2}{0}+\binom{n-2}{1}\right) + \dots$
$\displaystyle = a_0\binom{n-1}{0} + a_1\binom{n-1}{1} + \dots = \sum_{i=0}^{n-1} a_i \binom{n-1}{i}$
cioè la sommatoria nella prima riga.

Ora per induzione quella sommatoria è costante in tutto il sottotriangolo e da questo ricavo la tesi.

Fatemi sapere se la soluzione è corretta e chiara.....