$n$-words over the alphabet $\{0,...,d\}$ without consecutive $0$'s I'm trying to solve the following problem in chapter 3 of Aigner's A Course in Enumeration:
Let $f(n)$ be the number of $n$-words over the alphabet $\{0,1,2\}$ that contain no neighboring 0's. Determine $f(n)$. 
One is easily led to the recurrence $f(n)=2(f(n-1)+f(n-2))$ and the generating function $$F(x)=\frac{1+x}{1-2x-2x^2}.$$ At this point, I am trying to solve for $f(n)$. I used partial fractions to get
$$f(n)=\frac{1+\sqrt{3}}{2\sqrt{3}}(\frac{-1+\sqrt{3}}{2})^n+\frac{-1+\sqrt{3}}{2\sqrt{3}}(\frac{-1-\sqrt{3}}{2})^n$$
for $n\geq 2$, but I cannot reconcile this with Brian M. Scotts answer here: Recurrence relation for the number of ternary strings containing 2 consecutive zeros vs not containing
I also tried generalizing, by looking at the $n$-words over $\{0,...,m\}$ with no consecutive $0$'s. This leads one to the generating function $$F_m(x)=\frac{1+x}{1-mx-mx^2}.$$
Since my determination of $f(n)$ gives incorrect values, I made a mistake. After an hour of checking, I just cannot find it. Furthermore, Aigner gives the following answer $$f(n)=\sum_i(\binom{n+1}{2i+1}+\binom{n}{2i+1})3^i,$$
which cannot come from this fibonacci-like approach. Any ideas?
 A: Start with 
$${1+x\over 1-2x-2x^2}={\left({{1\over 2}+{1\over\sqrt{3}}}\right)\over 
1-x(1+\sqrt{3}) }+{\left({{1\over 2}-{1\over\sqrt{3}}}\right)\over 1-x(1-\sqrt{3}) } $$
to get
\begin{eqnarray*}p(n)&=&\left({{1\over 2}+{1\over\sqrt{3}}}\right)(1+\sqrt{3})^n+\left({{1\over 2}-{1\over\sqrt{3}}}\right)(1-\sqrt{3})^n\\[5pt]&=&{1\over 2}[(1+\sqrt{3})^n+(1-\sqrt{3})^n]+{1\over\sqrt{3}}[(1+\sqrt{3})^n-(1-\sqrt{3})^n]\\[5pt]
&=&\sum_j {n\choose 2j}\,3^j+\sum_j 2{n\choose 2j+1}\,3^j.
\end{eqnarray*}
A: It looks to me that you, Aigner and Brian Scott are all saying the same thing.
We have $f(n) = 2 f(n-1) + 2 f(n-2)$, together with $f(1)=3$ and $f(2)=8$, hence:
$$ \sum_{n\geq 1}f(n)\,x^n = \frac{3x+2x^2}{1-2x-2x^2}$$
and by partial fraction decomposition:
$$ f(n) = \left(11+\frac{14}{\sqrt{3}}\right)\left(\frac{-1+\sqrt{3}}{2}\right)^n + \left(11-\frac{14}{\sqrt{3}}\right)\left(\frac{-1-\sqrt{3}}{2}\right)^n. $$
In order to recover Aigner's representation as a weighted sum of binomial coefficients, it is enough to expand $(-1\pm\sqrt{3})^n$ by using the binomial theorem.
