# A combinatorial proof of the identity $\sum\limits_{k=0}^n\binom{2k}{k}\binom{2(n-k)}{n-k}=4^n$ [duplicate]

I have to prove that $$\sum_{k=0}^n\binom{2k}{k}\binom{2(n-k)}{n-k}=4^n$$ The questions also asks for an algebraic proof and I used induction for that algebraic proof. For a combinatorial proof I have no idea on how to proceed on it . The first thing I thought of using a set and considering $k$ subsets of it but that idea does not work here. I just want a hint and I would prefer not giving out the full answer.

• Think of base-4 numbers (the 4^n gives you that hint). To write such a number, you have to have some ODD digits and some EVEN digits? How many? Where are they? And what values do these have? Commented Feb 17, 2016 at 12:41
• @JohnHughes Any way of proving it without using base 4 numbers. I am actually not comfortable with change in bases Commented Feb 17, 2016 at 12:49
• OK. Think of sequences of $n$ colored balls, each ball being black, white, red, or green. In such a sequence, there have to be some black-or-white balls (possibly 0) and some red-or-green balls (also possibly 0, but not at the same time unless $n = 0$). Where these are located, and for each one, whether it's white (in the white-black set) or red (in the red-green set), are all things that might vary. How many different $n$-ball sequences are there? Commented Feb 17, 2016 at 13:03
• Okay I get it I think. For the first case (the black and white one)there are $2k$ places where the black and white set can be there and then to chose white from it,there are $k$ number of ways to do it. Now for the red green case there are $2(n-k)$ places where this set can be present. Because $k$ had already been chosen in the first case. Out of this $2(n-k)$ to chose a colour in this set there are $n-k$ ways to do it. By principle of multiplication it will become $\binom{2k}{k}\binom{2(n-k)}{n-k}$ number of ways to do the task. Now I have to take the sum since there can be many such k's. Commented Feb 17, 2016 at 13:54
• The comment was a bit big so I am continuing it here. Now since there are 4 choices for every ball in the n sequence of balls. There are $4^n$ ways of doing it. @JohnHughes (Please do read the above comment) Commented Feb 17, 2016 at 13:55

You can prove this identity using paths with steps of size $\pm1$. There are a total of $4^n$ such paths of length $2n$ starting at $(0,0)$. Partition this set of paths according to the final visit to the $x$-axis, call that position $(2k,0).$

It is pretty clear that the number of paths from $(0,0)$ to $(2k,0)$ is $2k\choose k$; this is the red part of the diagram. It is not so clear, but is true, that the number of paths of length $2n-2k$ that start at $(2k,0)$ and do not touch the $x$-axis is ${2(n-k)\choose n-k}$. This is the black part of the diagram.

To find a combinatorial argument for this identity has a long history. See the references below and also Phira's answer here. The following diagram fills a gap in my argument above by showing a bijection between balanced paths that start with an upstep and strictly positive paths.

Starting with a balanced path, keep the initial upstep, then color red until you reach the minimum value for the first time. Reverse the red section and swap the red and black sections, and connect them to create a strictly positive path.

Starting with a strictly positive path, keep the initial upstep. Now the path ends at $(2n,2a)$ for some $a>0$. Begin at the right and color red until you reach level $a$ for the first time. Reverse the red section and swap the red and black sections, and connect them to create a balanced path.

Similarly, balanced paths with an initial downstep are in one-to-one correspondence with strictly negative paths. Therefore the set of all balanced paths is in one-to-one correspondence with paths that don't touch the $x$-axis except at $(0,0)$.

1. Counting and Recounting: The Aftermath by Marta Sved, Math. Intelligencer 6 (1984), no. 4, 44–45.

2. Two New Bijections on Lattice Paths by Glenn Hurlbert and Vikram Kamat, arXiv:math/0609222 [math.CO]

• Masterful fifth sentence. :) Commented Feb 17, 2016 at 17:26
• Well, that's the flaw with this argument. I'm trying to think of the shortest proof of this fact.
– user940
Commented Feb 17, 2016 at 17:28

The generating function of the central binomial coefficients is $$\sum_{k\ge 0} \binom{2k}{k} x^k = {1\over \sqrt{1-4x}}$$ Multiplication of this series by itself gives : \eqalign{ \sum_{k\ge 0} \binom{2k}{k} x^k \cdot \sum_{k\ge 0} \binom{2k}{k} x^k &= {1\over 1-4x} \cr \sum_{n\ge 0} \biggl( \sum_{k = 0}^n\binom{2k}{k}\binom{2(n-k)}{n-k}\biggr)x^n &= {1\over 1-4x} \cr } Therefore the desired sum is the $n^{th}$ coefficient in the expansion of ${1\over 1-4x}$ which is $4^n$. That is : $$\sum_{k = 0}^n\binom{2k}{k}\binom{2(n-k)}{n-k} = 4^n$$