Q:

Is there any combinatorial consideration for this identity?

It is true that:
$$\sum_{i=0}^{[n/2]} {n-i \choose i} \times 2^i=\frac{1}{3}(2^{n+1}+(-1)^n)$$
It can be proven easily by induction. but is there any double counting argument or some direct proof for it?
Thanks...

A:

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\sum_{k = 0}^{\left\lfloor n/2\right\rfloor}{n - k \choose k}2^{k} =
{1 \over 3}\bracks{2^{n + 1} + \pars{-1}^{n}}:\ {\large ?}}$

With $\bbox[#dfd,10px]{\ds{0 < a < 1/2}}$:
\begin{align}
\sum_{k = 0}^{\left\lfloor n/2\right\rfloor}{n - k \choose k}2^{k} & =
\sum_{k = 0}^{\color{#f00}{n}}{n - k \choose k}2^{k} =
\sum_{k = 0}^{n}2^{k}\sum_{j = n}^{0}{j \choose k}\delta_{j,n - k} =
\sum_{j = 0}^{n}\sum_{k = 0}^{j}{j \choose k}2^{k}\,\delta_{n,k + j}
\\[5mm] & =
\sum_{j = 0}^{n}\sum_{k = 0}^{j}{j \choose k}2^{k}\oint_{\verts{z}\ =\ a}\
{1 \over z^{n + 1 - k - j}}\,{\dd z \over 2\pi\ic}
\\[5mm] & =
\oint_{\verts{z}\ =\ a}\ {1 \over z^{n + 1}}\sum_{j = 0}^{n}z^{\, j}
\sum_{k = 0}^{j}{j \choose k}\pars{2z}^{k}\,{\dd z \over 2\pi\ic}
\\[5mm] & =
\oint_{\verts{z}\ =\ a}\ {1 \over z^{n + 1}}\sum_{j = 0}^{n}z^{\, j}
\pars{1 + 2z}^{\, j}\,{\dd z \over 2\pi\ic}
\\[5mm] & =
\oint_{\verts{z}\ =\ a}\ {1 \over z^{n + 1}}
\sum_{j = 0}^{n}\pars{z + 2z^{2}}^{\, j}\,{\dd z \over 2\pi\ic}
\\[5mm] & =
\oint_{\verts{z}\ =\ a}\ {1 \over z^{n + 1}}
\,{\pars{z + 2z^{2}}^{n + 1} - 1 \over \pars{z + 2z^{2}} - 1}
\,{\dd z \over 2\pi\ic}
\\[5mm] & =
\oint_{\verts{z}\ =\ a}\ {1 \over z^{n + 1}}
\,{\pars{z + 2z^{2}}^{n + 1} - 1 \over 2\pars{z + 1}\pars{z - 1/2}}
\,{\dd z \over 2\pi\ic}
\\[5mm] & =
\underbrace{\oint_{\verts{z}\ =\ a}\
{\pars{1 + 2z}^{n} \over 2\pars{z + 1}\pars{z - 1/2}}
\,{\dd z \over 2\pi\ic}}_{\ds{=\ 0}}\ +\
\oint_{\verts{z}\ =\ a}\
{1 \over z^{n + 1}\pars{1 + z}\pars{1 - 2z}}
\,{\dd z \over 2\pi\ic}
\\[5mm] & =
{1 \over 3}\oint_{\verts{z}\ =\ a}\
{1 \over z^{n + 1}\pars{1 + z}}\,{\dd z \over 2\pi\ic} +
{2 \over 3}\oint_{\verts{z}\ =\ a}\
{1 \over z^{n + 1}\pars{1 - 2z}}\,{\dd z \over 2\pi\ic}
\\[5mm] & =
{1 \over 3}\,\pars{-1}^{n} + {2 \over 3}\,2^{n} =
\bbx{\ds{{1 \over 3}\bracks{2^{n + 1} + \pars{-1}^{n}}}}
\end{align}

