Solving binomial summation $\sum_{k=0}^{\lfloor{n/2}\rfloor} \binom{n-k}{k} 2^{n-k}$ How can we solve the sum
$$\sum_{k=0}^{\lfloor{n/2}\rfloor} \binom{n-k}{k} 2^{n-k}$$
The problem arose from a counting question, but I am unable to solve this sum.
Edit:
The counting problem was similar to what @Phicar has written, ie, I looked up and the question is equivalent to fibonacci tiling in two colours.
 A: Here's the "snake-oil" approach that uses generating functions:
\begin{align}
\sum_{n=0}^\infty \sum_{k=0}^{\lfloor{n/2}\rfloor} \binom{n-k}{k} 2^{n-k} z^n
&= \sum_{k=0}^\infty \sum_{n=2k}^\infty \binom{n-k}{k} 2^{n-k} z^n\\
&= \sum_{k=0}^\infty 2^{-k} \sum_{n=2k}^\infty \binom{n-k}{k} (2z)^n\\
&= \sum_{k=0}^\infty 2^{-k} \sum_{n=0}^\infty \binom{n+k}{k} (2z)^{n+2k}\\
&= \sum_{k=0}^\infty 2^{-k} \frac{(2z)^{2k}}{(1-2z)^{k+1}}\\
&= \frac{1}{1-2z} \sum_{k=0}^\infty \left(\frac{2z^2}{1-2z}\right)^k\\
&= \frac{1}{1-2z} \cdot \frac{1}{1-\frac{2z^2}{1-2z}}\\
&= \frac{1}{1-2z-2z^2}\\
&= \frac{1+\sqrt 3}{2\sqrt 3}\cdot\frac{1}{1-(1+\sqrt 3)z} - \frac{1-\sqrt 3}{2\sqrt 3}\cdot\frac{1}{1-(1-\sqrt 3)z}\\
&= \frac{1+\sqrt 3}{2\sqrt 3}\sum_{n=0}^\infty ((1+\sqrt 3)z)^n - \frac{1-\sqrt 3}{2\sqrt 3}\sum_{n=0}^\infty((1-\sqrt 3)z)^n,
\end{align}
which implies that $$\sum_{k=0}^{\lfloor{n/2}\rfloor} \binom{n-k}{k} 2^{n-k}=\frac{(1+\sqrt 3)^{n+1} - (1-\sqrt 3)^{n+1}}{2\sqrt 3}.$$
Note that the recurrence $A_n=2(A_{n-1}+A_{n-2})$ mentioned by @Phicar is implied by the denominator $1-2z-2z^2$ of the generating function, without prior knowledge of what the sequence counts.
A: Hint: This sum reminds me of Fibonacci but coloring with $2$ colors. so, basically we should be able to show that if your sequence is defined as $A_n$ then 
$$A_n=2(A_{n-1}+A_{n-2}).$$ If this is the case, then we are basically watching at the polynomial
$$x^2=2x+2,$$ with roots $1\pm \sqrt{3}.$ and so your sequence will have as an answer
$$A_n = \frac{(1+\sqrt{3})^{n+1}-(1-\sqrt{3})^{n+1}}{(1+\sqrt{3})-(1-\sqrt{3})}$$
