Find the generating function for the sequence $a_n$ which counts the number of bags containing $n$ pieces of fruit in which there is an odd number of apples, at most $1$ banana, and at least $1$ orange. Find $a_{40}$.

I came up with the equation $(x+x^3+x^5...)(1+x)(x+x^2+x^3+...)$ for the three fruits. Simplifying, it becomes $x^2(\frac{1}{1-x^2})(\frac{1-x^2}{1-x})(\frac{1}{1-x})$ and then to $\frac{x^2}{(1-x)^2}$.

Assuming my formula is correct, do I find $a_{40}$ by plugging $40$ into the $x$'s?


No, $a_{40}$ is the coefficient of $x^{40}$ of the Taylor expansion of $\frac{x^2}{(1-x)^2}$. You can find this by starting $\frac{1}{1-x}=\sum_{n=0}^\infty x^n=1+x+x^2+\dots$ and taking the derivative to get $$\frac{1}{(1-x)^2}=\sum_{n=0}^\infty nx^{n-1}$$ So, $$\frac{x^2}{(1-x)^2}=\sum_{n=0}^\infty nx^{n+1}$$ What is the coefficient of $x^{40}$?

  • $\begingroup$ if the exponent is $40$, would the coefficient be $39$? $\endgroup$ – LoudAnnoyance May 16 '19 at 15:33
  • $\begingroup$ Exactly, note that you can check this since you can actually count the number of combinations $(1,0,39),(1,1,38),(3,0,37),(3,1,36),\dots ,(37,0,3),(37,1,2),(39,0,1)$. $\endgroup$ – Julian Mejia May 16 '19 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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