Simplify $\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n – k}{k}x^k$

Question

I am trying to simplify $\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n – k}{k}x^k$ into some easy to evaluate form, say something similar to $(x + a)^n$ or a single expression, but am having difficulty with it. I also found this previous answer, which shows that for $x = 1$, the sum is $F_n$, though it's hard to generalise the combinatorics argument… How should I generalise this?

Answer 1

Fix $x$, let $a_n = \sum_{k=0}^{\lfloor n/2\rfloor}\binom{n - k}{k}x^k$, and let $A(z) = \sum_{n=0}^\infty a_n z^n$. Then \begin{align} A(z) &= \sum_{n=0}^\infty \sum_{k=0}^{\lfloor n/2\rfloor}\binom{n - k}{k}x^k z^n \\ &= \sum_{k=0}^\infty x^k \sum_{n=2k}^\infty \binom{n - k}{k} z^n \\ &= \sum_{k=0}^\infty x^k z^{2k} \sum_{n=0}^\infty \binom{n + k}{k} z^n \\ &= \sum_{k=0}^\infty x^k z^{2k} \frac{1}{(1-z)^{k+1}} \\ &= \frac{1}{1-z} \sum_{k=0}^\infty \left(\frac{x z^2}{1-z}\right)^k \\ &= \frac{1}{1-z} \cdot \frac{1}{1-x z^2/(1-z)} \\ &= \frac{1}{1-z-x z^2}. \end{align} For $x=1$, this is well-known to be the generating function for the Fibonacci numbers.