1
$\begingroup$

I'm not sure how to show that $[\sum\limits_{k = 0}^n\binom{n}{k}]^2=\sum\limits_{r = 0}^{2n}\binom{2n}{r}$. I've heard of $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$ but I still get nowhere. I have no idea where $r$ came from or why it's $2n$ above the sum.

$\endgroup$
  • $\begingroup$ From all the answers below, I understand it now. Thank you everyone! $\endgroup$ – cosmicbrownie Oct 3 '18 at 20:00
2
$\begingroup$

By using a basis propertie of Pascal's triangle the LHS can be written as

$$\left[\sum_{k=0}^n\binom{n}{k}\right]^2=[2^n]^2=2^{2n}=\sum_{r=0}^{2n}\binom{2n}{r}$$

The $r$ is just used as a new index to avoid confusions by naming two different variables $k$ for example.

$\endgroup$
4
$\begingroup$

Use $$\sum_{f=0}^g{g\choose f}=2^g$$ substituting appropriate values for $f,g$ on both sides of what you want to prove.

$\endgroup$
1
$\begingroup$

$$ \sum_{k=0}^n\binom{n}{r}x^r = (x+1)^n\Rightarrow (x+1)^{2n} = \sum_{k=0}^{2n}\binom{2n}{r}x^r $$

with $x = 1$

$\endgroup$
0
$\begingroup$

You could also do a combinatorial proof: given $n$ distinct dogs and $n$ distinct cats, how many ways can you choose a subset of all the animals to take for a walk?

$\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.