What does this binomial sum equal?

Question

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?

Answer 1

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.

Answer 2

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