2
$\begingroup$

Prove that : $$\binom {2n}{n}=\sum_{r=0}^n \left[\binom nr\right]^2.$$

Help me solving using generating functions.

I tried solving it as follows -

$$\sum_{r=0}^{n}\binom{n}{r}^2=\sum_{r=0}^{n}\binom{n}{r}\binom{n}{n-r}.$$

Now I dont know how to proceed by summing the coefficients to prove it using generating functions.

$\endgroup$
  • $\begingroup$ If you don't show that you have worked on the question, and say where you are blocked, the question will be closed. $\endgroup$ – Jean Marie May 6 '17 at 10:43
2
$\begingroup$

HINT:

Note that

$$(1+x)^{2n}=(1+x)^{n}(1+x)^n = \left(\sum\limits_{k=0}^{n}\binom{n}{k}x^{k}\right) \cdot \left(\sum\limits_{k=0}^{n}\binom{n}{k}x^{k}\right)$$

From the LHS it is clear that the coefficient before $x^n$ is $\binom{2n}{n}$, and from the RHS it is clear that it is just a sum of products of coefficients before $x^{k}$ and $x^{n-k}$ ($k = 0..n$) and thus it is equal to

$$\sum\limits_{k=0}^n\binom{n}{k}\binom{n}{n-k} = \sum\limits_{k=0}^n\left[\binom{n}{k}\right]^2$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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