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: Consider the set of binary strings of length $n$, $\{0,1\}^n.$ Consider the following family of sets $$A_i = \{x\in \{0,1\}^n: x=x_1x_2\wedge |x_1|_1=i\wedge |x_2|=i\},$$ where $|x|$ is the length of the string, $|x|_1$ is the number of $1$'s in the string and $x=x_1x_2$ means a concatenation of the strings $x_1,x_2.$
From the construction, is clear that $|A_i|=\binom{n-i}{i}2^i$ because $x_2$ is free with the restriction of it's length and $x_1$ has to have $i$ 1's, so you must choose the spots of the $1's.$
Now, suppose $x\in A_i\cap A_j$ with $i>j$ then $x=x_1x_2=x_3x_4$ but $x_3=x_1y$ because $i>j,$ but then $j=|x_3|_1\geq |x_1|_1=i$ which is a contradiction, so $A_i\cap A_j = \emptyset$ if $i\neq j$.So, we have that $$|A|=\left|\bigcup _{i=0}^n A_i\right|=\sum _{i=0}^n|A_i|=\sum _{i=0}^n\binom{n-i}{i}2^i,$$
We know, also that $A\subseteq \{0,1\}^n,$ So consider $B_n=\{0,1\}^n\setminus A,$ so strings in $B_n$ are characterized by $x\in B_n$ iff $\not \exists i$ such that $x\in A_i.$
Claim: $B_n = (\{0\}\times B_{n-1})\cup (\{1\}\times B_{n-2}\times\{0,1\}).$

By the claim above we know that $2^n = |A|+|B_n|$ and $|B_n|=|B_{n-1}|+2|B_{n-2}|,|B_1|=1,|B_2|=1$ by whatever method you like the most(generating functions or matrix exponentiation( the both of them encodes an induction :( ) $|B_n|=\frac{2^n-(-1)^n}{3}.$
So $3*2^n=(2+1)2^n=3|A|+2^n-(-1)^n$ which implies$2^{n+1}+(-1)^n=3|A|$ so $$\frac{2^{n+1}+(-1)^n}{3}=\sum _{i=0}^n\binom{n-i}{i}2^i.$$
P.S by doing this one can see that there should be an easier proof involving domino tilings. 
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}
