# Show that $\sum_{k=o}^n \binom{n}{k}^2 = \binom{2n}{n}$ [duplicate]

There is a hint for this ex.: using symmetry. I would appreciate another hint to take advantage of.

My approach so far:

Induction step:

$$\sum_{k=0}^{n+1} \binom{n+1}{k}^2$$

$$= 1 + \sum_{k=1}^{n+1} \binom{n+1}{k}^2$$

$$= 1 + \sum_{k=0}^{n} \binom{n+1}{k+1}^2$$

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

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

Now, I should simplify $$2\sum_{k=0}^{n} (\binom{n}{k}\binom{n}{k+1})$$ but I don't know how to proceed.

## marked as duplicate by Servaes, Arthur, user10354138, MathOverview, N. F. TaussigNov 4 '18 at 17:17

• $\binom{n}{k}^2=\binom{n}{k}\cdot\binom{n}{n-k}$ – Tito Eliatron Nov 4 '18 at 16:58
• Do you know an answer that uses induction? – RM777 Nov 4 '18 at 17:15

There is a great combinatoric interpretation of this problem! Consider a lattice grid. $$\binom{2n}{n}$$ is the number of ways to get from $$(0,0)$$ to $$(n,n)$$ by only taking steps to the rihgt and up: this is because a total of $$2n$$ steps must be taken, and $$n$$ of them must be "chosen" to be up, the rest will be to the right.

Now $$\binom{n}{k}$$ is the number of ways to get from $$(0,0)$$ to $$(n-k,k)$$; of $$n$$ steps, you select $$k$$ to be up, the rest ($$n-k$$) will be to the right.

If you want to continue from $$(n-k,k)$$ to $$(n,n)$$, there are $$n$$ steps left in your journey (we've taken $$n$$, and $$2n$$ total must be taken). Note that $$k$$ of these steps must be to the right, and the result will be up. There are $$\binom{n}{k}$$ ways to make this decision.

Thus there are $$\binom{n}{k}$$ ways to get to $$(n-k,k)$$ from the origin then $$\binom{n}{k}$$ ways to get from there to $$(n,n)$$. These selections are independent so the total number of paths to $$(n,n)$$ that pass through $$(n-k,k)$$ is $$\binom{n}{k}^2$$.

Every path to $$(n,n)$$ must pass through $$(n-k,k)$$ for exactly one value of $$k$$, so the desired result is gotten by summing over $$k$$.

Edit: the symmetry used is that the square with vertices $$(0,0),(0,n),(n,0),(n,n)$$ is symmetric about the line $$(a,b)$$ for $$a+b=n$$

• Thx I thought the only proof is the induction proof. Your expl. makes sense alright but does this verify the truth of your args? – RM777 Nov 4 '18 at 20:24