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

Question

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?

Answer 1

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

Answer 2

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