24. [10] Compute, in terms of $n$,
$$
\sum_{k=0}^{n}\binom{n-k}{k} 2^{k}
$$

Note that whenever $s<t,\binom{s}{t}=0$.
Answer:
$$
\frac{2 \cdot 2^{n}+(-1)^{n}}{3}
$$

Solution: 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.