Solving binomial summation $\sum_{k=0}^{\lfloor{n/2}\rfloor} \binom{n-k}{k} 2^{n-k}$

Question

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.

Answer 1

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})}$$

Answer 2

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.