HMMT February

Let $T_{n}=\sum_{k=0}^{n}\binom{n-k}{k} 2^{k}$. From Pascal's recursion for binomial coefficients, we can find $T_{n}=2 T_{n-2}+T_{n-1}$, with $T_{0}=1$ and $T_{1}=1$. The characteristic polynomial of this recursion is $x^{2}-x-2=0$, which has roots 2 and -1. Thus $T_{n}=a \cdot 2^{n}+b \cdot(-1)^{n}$ for some $a$ and $b$. From the initial conditions we have $a+b=1$ and $2 a-b=1$. It follows that $a=2 / 3$ and $b=1 / 3$, from which the conclusion follows.