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.