Solve generating function of $\left(1+x+x^2+...+x^{200}\right)*\left(1+x^2+x^4+...+x^{200}\right)$

70 Views Asked by At

So i want to find the coefficient of $x^{200}$ of the above generating function because I have the equation $2a+b=200$ and I want to find how many tuples(?) can give me that.

So I started using the definition of power series and I got $$\frac{1}{1-x}\cdot\frac{1}{1-x^2}$$ so I used partial fractions method and I got $$\frac{1}{\left(1-x\right)\left(1-x^2\right)} = \frac{A}{1-x}* \frac{Bx}{1-x^2}$$

Having said that I multiplied both parts with $1-x^2$ and I got $A=1$; however I can't do the same for $B$ and I need to find $x^{200}$, so?

1

There are 1 best solutions below

1
On

Partial fractions does help, but only as one step. The real trick is to recognize $1/(1-x)^2$ as the derivative of $1/(1-x)$. We have

$${1\over1-x}\cdot{1\over1-x^2}={1\over2}\cdot{1\over1-x}\left({1\over1-x}+{1\over1+x} \right)={1\over2}\left({1\over(1-x)^2}+{1\over1-x^2} \right)={1\over2}\left(\left(1\over1-x \right)'+{1\over1-x^2} \right)\\ ={1\over2}\left((1+x+x^2+\cdots)'+(1+x^2+x^4+\cdots) \right)\\ ={1\over2}\left((0+1+2x+\cdots+201x^{200}+\cdots)+(1+x^2+x^4+\cdots+x^{200}+\cdots) \right)$$

so the coefficient of $x^{200}$ is ${1\over2}(201+1)=101$.