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

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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).

Answer 5

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.