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?
Best Answer
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$.