0
$\begingroup$

I'm trying to evaluate this sum: $$\sum_{k=0}^n {n \choose k}{{2n+1}\choose k}$$

I thought I could work with generating functions of the two binomials. I know $$\sum_{k=0}^n\binom{n}k{}x^k=(1+x)^n$$ is the generating function for ${n \choose k}$ but I don't know how to find the one for $\binom{2n+1}{k}$ or if this would even be the correct way to evaluate this sum? Maybe there is an easier way?

$\endgroup$

2 Answers 2

5
$\begingroup$

It’s

$$\sum_k\binom{n}k\binom{2n+1}k=\sum_k\binom{n}{n-k}\binom{2n+1}k=\binom{3n+1}n$$

by Vandermonde’s identity.

$\endgroup$
1
  • $\begingroup$ @User: You’re welcome. $\endgroup$ Commented Feb 24, 2016 at 3:55
1
$\begingroup$

$$(1+x)^n\cdot(x+1)^{2n}=(1+x)^{3n}$$

$$\left(\sum_{k=0}^n {n \choose k}x^k\right)\cdot\left(\sum_{k=0}^{2n}\binom{2n}k x^{2n-k}\right)=\sum_{k=0}^{3n}\binom{3n}k x^{3n-k}$$

Consider the coefficients of $x^{2n}$

$$\sum_{k=0}^n {n \choose k}{{2n}\choose k}=\binom{3n}n$$

$\endgroup$
2
  • $\begingroup$ it's not $2n+1$ but $2n$ in the 2nd binomial $\endgroup$
    – G Cab
    Commented Dec 13, 2017 at 13:58
  • $\begingroup$ @GCab, Thanks for your observation $\endgroup$ Commented Dec 13, 2017 at 14:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .