Suppose we seek to evaluate
$$Y(n) = \sum_{k=1}^n 2^{n-k} {k\choose\lfloor k/2\rfloor},$$
by considering
$$Y_1(n) = \sum_{k=0}^{\lfloor n/2\rfloor}
2^{n-2k} {2k\choose k}
\quad\text{and}\quad
Y_2(n) = \sum_{k=0}^{\lfloor (n-1)/2\rfloor}
2^{n-2k-1} {2k+1\choose k}.$$
We will use the following Iverson bracket:
$$[[0\le k\le n]]
= \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{z^k}{z^{n+1}} \frac{1}{1-z} \; dz.$$
Evaluation of $Y_1(n).$
Introduce
$${2k\choose k} =
\frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{1}{w^{k+1}}
(1+w)^{2k} \; dw.$$
With the Iverson bracket controlling the range we can extend $k$ to
infinity to get for the sum
$$\frac{2^n}{2\pi i}
\int_{|w|=\epsilon}
\frac{1}{w}
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{\lfloor n/2\rfloor+1}} \frac{1}{1-z}
\sum_{k\ge 0} 2^{-2k} z^k \frac{(1+w)^{2k}}{w^k}
\; dz \; dw.$$
We can instantiate these contours to get convergence of the series.
We thus obtain
$$\frac{2^n}{2\pi i}
\int_{|w|=\epsilon}
\frac{1}{w}
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{\lfloor n/2\rfloor+1}} \frac{1}{1-z}
\frac{1}{1- z (1+w)^2 / w /4}
\; dz \; dw
\\ = \frac{2^{n+2}}{2\pi i}
\int_{|w|=\epsilon}
\frac{1}{(1+w)^2}
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{\lfloor n/2\rfloor+1}} \frac{1}{z-1}
\frac{1}{z- 4w/(1+w)^2}
\; dz \; dw.$$
We evaluate the inner piece by computing the negative of the sum of
the residues at $z=1,$ $z=4w/(1+w)^2$ and $z=\infty.$ We get for $z=1$
$$\frac{1}{1- 4w/(1+w)^2}
= \frac{(1+w)^2}{(1+w)^2- 4w}
= \frac{(1+w)^2}{(1-w)^2}$$
for a zero contribution.
We get for $z=\infty$
$$-\mathrm{Res}_{z=0}
\frac{1}{z^2}
\frac{1}{1/z^{\lfloor n/2\rfloor+1}} \frac{1}{1/z-1}
\frac{1}{1/z- 4w/(1+w)^2}
\\ = -\mathrm{Res}_{z=0}
z^{\lfloor n/2\rfloor+1} \frac{1}{1-z}
\frac{1}{1- 4wz/(1+w)^2}$$
again for a zero contribution.
Finally for $z=4w/(1+w)^2$ we get
$$-\frac{(1+w)^{2\lfloor n/2\rfloor+2}}
{2^{2\lfloor n/2\rfloor+2} \times w^{\lfloor n/2\rfloor+1}}
\frac{(1+w)^2}{(1-w)^2}.$$
Substitute into the outer integral to obtain
$$-\frac{2^{n\mod 2}}{2\pi i}
\int_{|w|=\epsilon}
\frac{(1+w)^{2\lfloor n/2\rfloor+2}}
{w^{\lfloor n/2\rfloor+1}}
\frac{1}{(1-w)^2} \; dw.$$
Extracting the negative of the residue we get the sum
$$2^{n\mod 2}\sum_{q=0}^{\lfloor n/2\rfloor}
{2\lfloor n/2\rfloor+2\choose q}
(\lfloor n/2\rfloor-q+1).$$
This yields
$$2^{n\mod 2} (\lfloor n/2\rfloor+1)
\frac{1}{2} \left(2^{2\lfloor n/2\rfloor+2}
- {2\lfloor n/2\rfloor+2\choose \lfloor n/2\rfloor+1} \right)
\\ - 2^{n\mod 2} (2\lfloor n/2\rfloor+2)
\sum_{q=1}^{\lfloor n/2\rfloor}
{2\lfloor n/2\rfloor+1\choose q-1}
\\ = 2^{n\mod 2} (\lfloor n/2\rfloor+1)
\frac{1}{2} \left(2^{2\lfloor n/2\rfloor+2}
- {2\lfloor n/2\rfloor+2\choose \lfloor n/2\rfloor+1} \right)
\\ - 2^{n\mod 2} (\lfloor n/2\rfloor+1)
\left(2^{2\lfloor n/2\rfloor+1}
- 2{2\lfloor n/2\rfloor+1\choose \lfloor n/2\rfloor } \right)
\\ = 2^{n\mod 2} (\lfloor n/2\rfloor+1)
\left(2 - \frac{1}{2}
\frac{2\lfloor n/2\rfloor+2}{\lfloor n/2\rfloor+1} \right)
{2\lfloor n/2\rfloor+1\choose \lfloor n/2\rfloor }
\\ = 2^{n\mod 2} (\lfloor n/2\rfloor+1)
{2\lfloor n/2\rfloor+1\choose \lfloor n/2\rfloor }.$$
Evaluation of $Y_2(n).$
This is obviously very similar to the first case.
We get the integral
$$\frac{2^{n+1}}{2\pi i}
\int_{|w|=\epsilon}
\frac{1}{1+w}
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{\lfloor (n-1)/2\rfloor+1}} \frac{1}{z-1}
\frac{1}{z- 4w/(1+w)^2}
\; dz \; dw.$$
There is no contribution from $z=1$ and $z=\infty$ as before
which leaves
$$-\frac{2^{(n+1)\mod 2}}{2\pi i}
\int_{|w|=\epsilon}
\frac{(1+w)^{2\lfloor (n-1)/2\rfloor+3}}
{w^{\lfloor (n-1)/2\rfloor+1}}
\frac{1}{(1-w)^2} \; dw.$$
Extracting the negative of the residue we obtain
$$2^{(n+1) \mod 2}
\sum_{q=0}^{\lfloor (n-1)/2\rfloor}
{2\lfloor (n-1)/2\rfloor+3\choose q}
(\lfloor (n-1)/2\rfloor-q+1).$$
This yields
$$2^{(n+1) \mod 2} (\lfloor \frac{n-1}{2}\rfloor +1)
\times \frac{1}{2}
\left(2^{2\lfloor \frac{n-1}{2}\rfloor+3}
- 2 {2\lfloor \frac{n-1}{2}\rfloor+3\choose \lfloor \frac{n-1}{2}\rfloor +1}\right)
\\ - 2^{(n+1) \mod 2} (2\lfloor \frac{n-1}{2}\rfloor+3)
\sum_{q=1}^{\lfloor \frac{n-1}{2}\rfloor}
{2\lfloor \frac{n-1}{2}\rfloor+2 \choose q-1}
\\ = 2^{(n+1) \mod 2} (\lfloor \frac{n-1}{2}\rfloor +1)
\times \frac{1}{2}
\left(2^{2\lfloor \frac{n-1}{2}\rfloor+3}
- 2 {2\lfloor \frac{n-1}{2}\rfloor+3\choose \lfloor \frac{n-1}{2}\rfloor +1}
\right)
\\ - 2^{(n+1) \mod 2} (2\lfloor \frac{n-1}{2}\rfloor+3)
\\ \times \frac{1}{2} \left(2^{2\lfloor \frac{n-1}{2}\rfloor+2}
- 2{2\lfloor \frac{n-1}{2}\rfloor+2 \choose \lfloor \frac{n-1}{2}\rfloor}
- {2\lfloor \frac{n-1}{2}\rfloor+2 \choose \lfloor \frac{n-1}{2}\rfloor+1}
\right).$$
Evaluation of $Y(n).$
Keeping in mind that $Y(n)$ does not include a term for $k=0$ we get for
$n = 2p$ the contributions
$$-2^{2p} + (p+1) {2p+1\choose p}
+ p \left(2^{2p+1} - 2 {2p+1\choose p}\right)
\\ - (2p+1) \left(2^{2p} - 2 {2p\choose p-1} - {2p\choose p}\right)
\\ = -2^{2p+1} + (4p+2){2p\choose p}.$$
On the other hand for $n = 2p+1$ we obtain
$$-2^{2p+1} + 2 (p+1) {2p+1\choose p}
+ \frac{1}{2} (p+1) \left(2^{2p+3} - 2 {2p+3\choose p+1} \right)
\\ - \frac{1}{2} (2p+3)
\left(2^{2p+2} - 2{2p+2\choose p} - {2p+2\choose p+1}\right)
\\ = -2^{2p+2} + (4p+5) {2p+1\choose p}.$$
Joining the two formulae we get the compact closed form
$$-2^{n+1} + (2n + 2 + (n\mod 2))
{n\choose \lfloor n/2\rfloor}.$$
I would conjecture that with the closed form being this simple now
that it has been computed we can probably find a much more elegant
proof.
