For evaluating $\sum^n_{k=0}{n\choose{k}}{m\choose{k}}$ for fixed $m,n$, I got ${n+m\choose{n}}$, does it look right?

I rewrite it as $\sum^n_{k=0}{n\choose{n-k}}{m\choose{k}}$, that's what I did.

  • $\begingroup$ Looks right, good job, do you understand the combinatorial concepts behind it though? $\endgroup$ – user67258 Jun 15 '13 at 4:39
  • 3
    $\begingroup$ I think that $(1+\nu)^n(1+\nu)^{m}=(1+\nu)^{n+m}$ is useful. $\endgroup$ – Gaston Burrull Jun 15 '13 at 4:43
  • $\begingroup$ (The question I linked to is more recent, but has more answers and is already a duplicate target, so I thought this sense of closure made more sense.) $\endgroup$ – Arnaud D. Nov 8 '18 at 11:17

I think you can have combinatorial arguments for it if you rewrite the expression as $$ \sum_{k=0}^n \begin{pmatrix} n\\ n-k \end{pmatrix} \begin{pmatrix} m\\ k \end{pmatrix} $$ This is just equal to choosing $n$ objects out of $n + m $ of them, thus making it equal to $ \begin{pmatrix} n+m\\ n \end{pmatrix}$, first keep a particular choice of $m$ objects aside from the rest $n $ objects, then choose some ( say $k$ of them ) from the set of $m$ objects and rest from the set of $n$ objects. This you can do for all $ 0\leq k\leq n $, thus you obtain the expression.


Not the answer you're looking for? Browse other questions tagged or ask your own question.