<s>[INST] 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?
 [/INST] 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}.}$$
</s>