# Prove that $\sum_{k=0}^n 2^k \binom{n}{k} \binom{n-k}{\lfloor (n-k)/2 \rfloor}=\binom{2n+1}{n}$

Where the thing that looks like a floor function is the floor function. This is an interesting result which I hoped to prove by induction, but ran into trouble applying the inductive hypothesis. The base case is trivial. Here's the progress I made:

Inductive hypothesis: $$\sum_{k=0}^m 2^k \binom{m}{k} \binom{m-k}{\lfloor{(m-k)/2}\rfloor}=\binom{2m+1}{m}$$ for some $$m>0$$. Then \begin{align*} &\sum_{k=0}^{m+1} 2^k \binom{m+1}{k} \binom{m+1-k}{\lfloor{(m+1-k)/2}\rfloor}\\ =&\sum_{k=0}^m 2^k \binom{m+1}{k} \binom{m+1-k}{\lfloor{(m+1-k)/2}\rfloor}+2^{m+1} \binom{m+1}{m+1} \binom{m+1-m+1}{\lfloor{(m+1-(m+1))/2}\rfloor}\\ =&2^{m+1}+\sum_{k=0}^m 2^k \binom{m+1}{k} \binom{m+1-k}{\lfloor{(m+1-k)/2}\rfloor} \end{align*} Let $$A$$ be the set of all $$k\in[0,m]$$ such that $$m+1-k$$ is even. Let $$B$$ be the set of $$k\in[0,m]$$ such that $$m+1-k$$ is odd. Observe that for each $$k\in[0,m]$$, $$k$$ is in exactly one of $$A$$ or $$B$$. It follows that \begin{align*} &\sum_{k=0}^m 2^k \binom{m+1}{k} \binom{m+1-k}{\lfloor{(m+1-k)/2}\rfloor}\\ =&\sum_{k\in A} 2^k \binom{m+1}{k} \binom{m+1-k}{\lfloor{(m+1-k)/2}\rfloor}+\sum_{k\in B} 2^k \binom{m+1}{k} \binom{m+1-k}{\lfloor{(m+1-k)/2}\rfloor}\\ =&\sum_{k\in A} 2^k \binom{m+1}{k} \binom{m+1-k}{(m+1-k)/2}+\sum_{k\in B} 2^k \binom{m+1}{k} \binom{m+1-k}{(m-k)/2} \end{align*}

Splitting the sum into $$A$$ and $$B$$ was a last-ditch attempt to form the expression into something to which I could apply the inductive hypothesis. Did I make a mistake somewhere, is this the wrong approach, or am I just missing the next step?

## 2 Answers

There are $$2n+1 \choose n$$ strings consisting of $$n$$ ones and $$n+1$$ zeroes.

Given any such string $$S$$, let $$S_1$$ consist of the first $$n$$ digits of the string $$S$$ and let $$S_2$$ consist of the last $$n+1$$ digits of $$S$$. Suppose that there $$k$$ values of $$i$$ such that the $$i^{th}$$ element of $$S_1$$ is different from the $$i^{th}$$ element of $$S_2$$. Then there are $$n \choose k$$ ways to choose which digits $$i$$ the two strings differ at. There are $$2^k$$ ways to assign these $$k$$ elements in $$S_1$$.

Now consider the number of ways in which the rest of the elements may be chosen. We need to choose the remaining $$n-k$$ elements of $$S_1$$ (which are the same as their respective elements in $$S_2$$) and the last element of $$S_2$$. The number of zeroes must be one greater than the number of ones. It can be shown that the number of ways to do this is $$n-k \choose \lfloor\frac{n-k}{2}\rfloor$$.

Seeking to verify

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

we observe that

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

We get

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

This yields two pieces:

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

and

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

We write for the first one

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

Now the coefficient extractor enforces the upper limit of the sum and we find

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

The second one is of course very similiar:

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

Once more the coefficient extractor enforces the upper limit of the sum and we find

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

Adding the two binomial coefficients we indeed obtain

$$\bbox[5px,border:2px solid #00A000]{ {2n+1\choose n}.}$$