The set of binary string whose integer representations are multiples of 3 have the generating function
$$\Phi_S(x)={1-x-x^2 \over 1-x-2x^2}$$
Let $a_n=[x^n]\Phi_s(x)$ represent the number of strings in $S$ with length $n$. Using partial fraction expansion to determine an explicit formula for $a_n$ for all integers $n\geq 0$. You may use the initial conditions $a_0=1$, $a_1=0$.
Hmm. What are the initial conditions for? How are partial fractions and generating functions related to recurrences? The terms do seem to follow $a_n=a_{n-1}+2a_{n-2}$ but how to prove it?
Note that we get very lucky, since $1-x-2x^2=(1-2x)(1+x)$.
The first step, since the numerator has degree $\ge $ the degree of the denominator, is to divide. We get $$\frac{1-x-x^2}{1-x-2x^2}=\frac{1}{2}+\frac{1}{2}\frac{1-x}{1-x-2x^2}.$$
We now work for a while with the simpler $\frac{1-x}{1-x-2x^2}$, We try to find $A$ and $B$ such that $$\frac{1-x}{1-x-2x^2}=\frac{A}{1+x}+\frac{B}{1-2x}=\frac{A(1+x)+B(1-2x)}{1-x-2x^2}.$$ So we want to have $$1-x \quad\text{identically equal to}\quad A(1+x)+B(1-2x).$$ Put $x=\frac{1}{2}$. We get $A=\frac{1}{3}$. Putting $x=-1$, or otherwise, we find that $B=\frac{2}{3}$.
Now use the fact that $$\frac{1}{1-t}=1+t+t^2+t^3+\cdots,$$ putting in turn $t=-x$ and $t=2x$, to find the power series expansions of $\frac{1}{1+x}$ and $\frac{1}{1-2x}$.
Finally, use our previous calculations to find the power series expansion of our original function. From this we can read off the coefficient of $x^k$ for any $k$. Note that our original function is equal to $$\frac{1}{2}+\frac{1}{6}\cdot\frac{1}{1+x}+\frac{1}{3}\cdot\frac{1}{1-2x}.$$