How can a 15 year old construe the LHS of Generalized Vandermonde’s Identity, when it lacks summation limits and a summation index

combinatorics

Paradoxically, though the Rothe-Hagen Identity,

$\sum\limits_{k=0}^n\frac{x}{x+kz}{x+kz \choose k}\frac{y}{y+(n-k)z}{y+(n-k)z \choose n-k}=\frac{x+y}{x+y+nz}{x+y+nz \choose n}$

generalizes the Generalized Vandermonde Identity,

$\sum\limits_{k_1+\cdots +k_p = m} {n_1\choose k_1} {n_2\choose k_2} \cdots {n_p\choose k_p} = { n_1+\dots +n_p \choose m }$

Rothe-Hagen Identity is more intelligible than the Generalized Vandermonde Identity for my 15 year old. A 15 y.o. can effortlessly write any term of the Rothe-Hagen Identity, by substituting the lower limits for all $k$ in the addend. When $k = 0$, just input $k = 0$ in the addend. When $k = n$, just swap all $k$'s in the addend with $n$'s!

But how can a 15 y.o. interpret the left hand side of the Generalized Vandermonde Identity? Or even write the first few terms of the left hand side of the Generalized Vandermonde Identity? It contains no lower and upper limits of summation, and no summation index. The Generalized Vandermonde Identity contains no $k$, unlike the Rothe-Hagen Identity!

Best Answer

I think you are confused as to what the notation $$ \sum_{k_1+k_2+\dots+k_p=m}\cdots $$ means. It means that the summation ranges over all lists of nonnegative* integers $(k_1,k_2,\dots,k_p)$ for which $k_1+\dots+k_p=m$.

Let's look at a smallish example, say $p=3$ and $m=2$. You can check there are exactly six triples of nonnegative integers whose sum is $2$. They are $$ (0,0,2),(0,2,0),(2,0,0),\\(1,1,0),(1,0,1),(0,1,1), $$ This means that the left hand side of the GVI sum is $$ \binom{n_1}{0}\binom{n_2}{0}\binom{n_3}2+ \binom{n_1}{0}\binom{n_2}{2}\binom{n_3}0+ \binom{n_1}{2}\binom{n_2}{0}\binom{n_3}0+\\ \binom{n_1}{1}\binom{n_2}{1}\binom{n_3}0+ \binom{n_1}{1}\binom{n_2}{0}\binom{n_3}1+ \binom{n_1}{0}\binom{n_2}{1}\binom{n_3}1\;\;\;\; $$ and that GVI claims the above sum is equal to $\binom{n_1+n_2+n_3}{2}$.

* How did I know that they had to be nonnegative integers? Mostly from experience. However, the fact that expression inside the sum contains $\binom{n_i}{k_i}$ means that effectively, the $k_i$ must be nonnegative.

Related Question