Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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}.$$

share|improve this answer
    
Thanks for the hint! I think I got the partial fractions part. So the part about initial conditions was purposefully misleading? –  user54609 Jun 21 '13 at 1:53
1  
Initial conditions are not needed if we have the full generating function, since the generating function tells us, though sometimes with reluctance, all values. –  André Nicolas Jun 21 '13 at 1:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.