<s>[INST] Identities involving binomial coefficients, floors, and ceilings I found the following four apparent identities:
$$
\begin{align}
\sum_{k=0}^n
  2^{-\lfloor\frac{n+k}{2}\rfloor}
     {\lfloor\frac{n+k}{2}\rfloor\choose k}
&=
\frac{4}{3}-\frac{1}{3}(-2)^{-n},\\
\sum_{k=0}^n
  2^{-\lceil \frac{n+k}{2}\rceil }
     {\lfloor\frac{n+k}{2}\rfloor\choose k}
&=
1,\\
\sum_{k=0}^n
  2^{-\lfloor\frac{n+k}{2}\rfloor}
     {\lceil \frac{n+k}{2}\rceil \choose k}
&=
2-2^{-n},\\
\sum_{k=0}^n
  2^{-\lceil \frac{n+k}{2}\rceil }
     {\lceil \frac{n+k}{2}\rceil\choose k}
&=
\frac{4}{3}-\frac{1}{3}(4)^{-\lfloor\frac{n}{2}\rfloor}.
\end{align}
$$
I want to know how to prove them. I also want to know whether they have  (after multiplying both sides by $2^n$) nice combinatorial interpretations.
 [/INST] Assuming that $n$ is even, $n=2m$, we have:
$$\begin{eqnarray*} \sum_{k=0}^{n} 2^{-\left\lfloor\frac{n+k}{2}\right\rfloor}\binom{\left\lfloor\frac{n+k}{2}\right\rfloor}{k}&=&\sum_{j=0}^{m}2^{-(m+j)}\binom{m+j}{2j}+\sum_{j=0}^{m-1}2^{-(m+j)}\binom{m+j}{2j+1}\\&=&4^{-m}+2^{-m}\sum_{j=0}^{m-1}2^{-j}\binom{m+j+1}{m-j}\\&=&4^{-m}+4^{-m}\sum_{j=1}^{m}2^j\binom{2m+1-j}{j}\end{eqnarray*}$$
so your sums can be computed by using Fibonacci polynomials.
</s>