# Algebraic proof of $\sum_{k}\binom{n}{2k}\binom{2k}{k}2^{n-2k}=\binom{2n}n$ (Combinatoric proof is given)

I had a IMO training about double counting. Then, there is a problem which I hope there is a combinatoric proof. Here comes the problem:

For every positive integer $$n$$, let $$f\left(n\right)$$ be the number of all positive integers with exactly $$2n$$ digits, each having exactly $$n$$ of digits equal to $$1$$ and the other equal to $$2$$. Let $$g\left(n\right)$$ be the number of all positive integers with exactly $$n$$ digits, each of its digits can only be $$1,2,3$$ or $$4$$ and the number of $$1$$'s equals the number of $$2$$'s. Prove that $$f\left(n\right)=g\left(n\right)$$.

It is obvious to see that $$f\left(n\right)=\binom{2n}{n}$$, and $$g\left(n\right)=\sum_{k\le\lfloor\frac{n}{2}\rfloor}\binom{n}{2k}\binom{2k}{k}2^{n-2k}$$. However, it is hard to prove this in an algebraic way. I hope there are someone to prove it by algebraic way. Thank you!

Combinatoric proof

We can establish a one-to-one correspondence between $$f\left(n\right)$$ and $$g\left(n\right)$$.

Let $$F\left(n\right)$$ be the set of all positive integers with exactly $$2n$$ digits, each having exactly $$n$$ of digits equal to $$1$$ and the other equal to $$2$$.

Also, let $$G\left(n\right)$$ be the set of all positive integers with exactly $$n$$ digits, each of its digits can only be $$1,2,3$$ or $$4$$ and the number of $$1$$'s equals the number of $$2$$'s.

Then, we can do this operation for all numbers in $$F\left(n\right)$$:
For every two digits of the numbers in $$F\left(n\right)$$, $$\begin{cases}11\Rightarrow 1\\22\Rightarrow 2\\12\Rightarrow 3\\21\Rightarrow 4\end{cases}$$ Then all the numbers will change into a set which is totally same as $$G\left(n\right)$$, as we find that the difference between the number of $$1$$'s and $$2$$'s doesn't change at all.

Therefore, we make a one-to-one correspondence between $$F\left(n\right)$$ and $$G\left(n\right)$$.

• Have you tried using induction? Commented Oct 16, 2019 at 14:59
• You could try showing that your sum for $g(n)$ has generating function $1/\sqrt{1-4z}$, which is the known generating function for $\binom{2n}{n}$. Commented Oct 16, 2019 at 15:00
• @RobPratt Side question, you would have to prove this statement to use it on the IMO, right? Is that possible using IMO-level math? I am asking because I have no experience with math contests. Commented Oct 16, 2019 at 15:05
• I don't know the rules of IMO, but the combinatorial proof is probably what they were looking for. Commented Oct 16, 2019 at 15:58
• I just want to have an algebraic proof. Also, it is just a selection test question Commented Oct 16, 2019 at 16:03

Here is the generating function approach: \begin{align} \sum_{n=0}^\infty \left(\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k}\binom{2k}{k} 2^{n-2k}\right) z^n &= \sum_{k=0}^\infty \binom{2k}{k} 2^{-2k} \sum_{n=2k}^\infty \binom{n}{2k}(2z)^n \\ &= \sum_{k=0}^\infty \binom{2k}{k} 2^{-2k} \frac{(2z)^{2k}}{(1-2z)^{2k+1}} \\ &= \frac{1}{1-2z} \sum_{k=0}^\infty \binom{2k}{k} \left[\left(\frac{z}{1-2z}\right)^2\right]^k \\ &= \frac{1}{1-2z} \cdot \frac{1}{\sqrt{1-4(z/(1-2z))^2}} \\ &= \frac{1}{\sqrt{1-4z}} \\ &= \sum_{n=0}^\infty \binom{2n}{n}z^n. \end{align} Hence $$\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k}\binom{2k}{k} 2^{n-2k} = \binom{2n}{n}$$ for all $$n$$.

• Nice solution. (+1) Commented Oct 16, 2019 at 20:04

Here is a slightly different proof that

$$\sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} {2k\choose k} 2^{n-2k} = {2n\choose n}.$$

We observe that

$${n\choose 2k} {2k\choose k} = \frac{n!}{(n-2k)! \times k! \times k!} = {n\choose k} {n-k\choose n-2k}.$$

We get for our sum

$$\sum_{k=0}^{\lfloor n/2\rfloor} {n\choose k} {n-k\choose n-2k} 2^{n-2k} \\ = \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose k} [z^{n-2k}] (1+z)^{n-k} 2^{n-2k} \\ = [z^n] (1+z)^n \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose k} z^{2k} (1+z)^{-k} 2^{n-2k}.$$

Now when $$2k\gt n$$ we get zero from the coefficient extractor, which enforces the range, so we continue with

$$2^n [z^n] (1+z)^n \sum_{k\ge 0} {n\choose k} z^{2k} (1+z)^{-k} 2^{-2k} \\ = 2^n [z^n] (1+z)^n \left(1+\frac{z^2}{2^2(1+z)}\right)^n \\ = 2^n [z^n] \frac{(2^2+2^2z+z^2)^n}{2^{2n}} = 2^n [z^n] \frac{(z+2)^{2n}}{2^{2n}} = 2^n {2n\choose n} 2^{2n-n} \frac{1}{2^{2n}} \\ = {2n\choose n}.$$

This is the claim.

Another proof. We seek to prove that

$$\sum_{k=0}^{\lfloor n/2\rfloor} 2^{n-2k} {n\choose 2k} {2k\choose k} = {2n\choose n}.$$

We get for the LHS

$$2^n [z^n] (1+z)^n \sum_{k\ge 0} 2^{-2k} z^{2k} {2k\choose k}.$$

Here we have extended to infinity due to the coefficient extractor. Continuing,

$$2^n [z^n] (1+z)^n \frac{1}{\sqrt{1-z^2}}.$$

This is

$$2^n \; \underset{z}{\mathrm{res}} \; \frac{1}{z^{n+1}} (1+z)^n \frac{1}{\sqrt{1-z^2}}.$$

Now put $$z/(1+z) = w$$ so that $$z=w/(1-w)$$ and $$1+z=1/(1-w)$$ as well as $$dz = 1/(1-w)^2 \; dw$$ to get

$$2^n \; \underset{w}{\mathrm{res}} \; \frac{1}{w^{n+1}} (1-w) \frac{1}{\sqrt{1-w^2/(1-w)^2}} \frac{1}{(1-w)^2} \\ = 2^n \; \underset{w}{\mathrm{res}} \; \frac{1}{w^{n+1}} \frac{1}{\sqrt{(1-w)^2-w^2}} \\ = 2^n \; \underset{w}{\mathrm{res}} \; \frac{1}{w^{n+1}} \frac{1}{\sqrt{1-2w}} \\ = 2^n [w^n] \frac{1}{\sqrt{1-2w}} = [w^n] \frac{1}{\sqrt{1-4w}} = {2n\choose n}.$$

This is the claim.

Claim 2 in the second solution to Exercise 2 from Fall 2018 UMN Math 5705 homework set #2 states the following:

Claim 2: Let $$n \in \mathbb N$$ and $$u \in \mathbb Z$$. Then, \begin{align} \sum_{k=0}^n 2^{n-2k-u} \dbinom{n}{2k+u} \dbinom{2k+u}{k} = \dbinom{2n}{n+u} . \end{align}

Your identity is a particular case of this when $$u$$ is taken to be $$0$$.

Claim 2 is also Theorem 2 in https://artofproblemsolving.com/community/c6h87265 , but the version of the proof in my homework set is better IMHO. Either way, the algebraic proof proceeds by induction on $$n$$, with the induction step being chiefly about rewriting $$\dbinom{n+1}{2k+u}$$ as $$\dbinom{n}{2k+u-1} + \dbinom{n}{2k+u}$$, then doing the same with $$\dbinom{2k+u}{k}$$ in one of the resulting sums, and a couple more such transformations at the very end when it comes to collecting terms. It is a completely unremarkable computation.

Yet another proof:

\begin{align*} \binom{2n}{n} &= [x^n](1+x)^{2n} \\ &= [x^n]((1+x^2) + 2x)^n \\ &= \sum_{j=0}^n \binom{n}{j} 2^{n-j} [x^n]\left(x^{n-j}(1+x^2)^j\right) \\ &= \sum_{j=0}^n \binom{n}{j} 2^{n-j} [x^j](1+x^2)^j \\ &= \sum_{\substack{0 \leq j \leq n \\ j \text{ even}}} \binom{n}{j} \binom{j}{j/2} 2^{n-j} \end{align*}

I think this approach corresponds most closely to the logic of your combinatorial proof, in that we can interpret $$1$$ as $$1$$ and $$2$$ as $$x$$ in the product $$(1 + x)^{2n}$$, and we proceed by pairing off consecutive factors: $$11 \mapsto 1$$, $$22 \mapsto x^2$$, $$12 \mapsto x$$ and $$21 \mapsto x$$. In the first version, taking the coefficient of $$x^n$$ corresponds to considering the sequences with the same number of $$1$$'s and $$2$$'s, while in the second version it corresponds to considering the sequences with the same number of $$11$$'s and $$22$$'s (disregarding the $$12$$'s and $$21$$'s, i.e. the $$3$$'s and $$4$$'s).

Alternative Proof

\begin{aligned} \sum_{k}\binom{n}{2k}\binom{2k}{k}2^{n-2k} &=\left[x^{0}\right]\left(2+\left(x+\frac{1}{x}\right)\right)^{n}\\ &=\left[x^{0}\right]\frac{\left(1+x\right)^{2n}}{x^{n}}\\ &=\left[x^{n}\right]\left(1+x\right)^{2n}\\ &=\binom{2n}{n} \end{aligned}

Alternative Combinatorial Proof

Split $$n$$ pairs of husband and wife evenly into two groups. You can directly split everyone evenly into two groups. The number of possible grouping is given by the RHS:

$$\binom{2n}{n}$$

You can also assign $$k$$ pairs to the first group, $$k$$ pairs to the second group, then split the remaining $$n-2k$$ pairs to the two groups. The number of possible assignment is given by the summand of LHS:

$$\binom{n}{2k}\binom{2k}{k}2^{n-2k}$$

Sum for all possible values of $$k$$ and you will get all possible groupings. Therefore LHS and RHS count the same objects and must be equal.