Using a generating function, how many ways can you make change for a dollar using pennies, nickels, dimes, quarters, and half-dollars? so far i got (1+x+x^2+x^3+...+x^100)

Question

Using a generating function, how many ways can you make change for a dollar using pennies, nickels, dimes, quarters, and half-dollars? so far i got (1+x+x^2+x^3+...+x^100) <- pennies 
(1+x^5+x^10+...+x^100) <- nickels 
(1+x^10+x^20+...+x^100) <- dimes 
(1+x^25+x^50+x^75+x^100) <- quarters 
(1+x^50+x^100) <- half dollars

and the generating function is: 1/(1-x)(1-x^5)(1-x^10)(1-x^25)(1-x^50)

what I need help is what do I do from here to get the answer I need? Please explain each step you did

tkhunny · Answer

Hmmm...  I like your original FINITE polynomials, but I'm not quite sure how you managed that Generating Function.  1/(1-x) does not result in a finite series.

anonymous · Answer

the pennies can be written as 1/(x-1)

tkhunny · Answer

Rethink.  $$1 + x + x^2 + ... + x^{100} = \frac{1-x^{101}}{1-x}$$

anonymous · Answer

http://aleph.math.louisville.edu/teaching/2009FA-681/notes-090917.pdf question 3 and answer 3

tkhunny · Answer

Please read more carefully.  It is the case that $$1 + x + x^{2} + ... + x^{100} = \frac{1 - x^{101}}{1-x}$$ as I have stated it.  It is also the case that $$1 + x + x^{2} + ... = \frac{1}{1-x}$$  It is also the case that in some cases it is simpler to work with the infinite form, rather than the more cumbersome finite form.

anonymous · Answer

well if i had it right earlier then can you tell me how to do the next step then?

tkhunny · Answer

If it were me, I'd use that result you posted in the link and divide out the dollar factor.  I am not aware of any easy way to pick out one coefficient amongst the hundreds presented in this complicated expression.

anonymous · Answer

thats the problem i am having what i really wanted to know is how to multiply this out to find the coefficient of x^100

(1+x+x^2+x^3+...+x^100)(1+x^5+x^10+...+x^100)(1+x^10+x^20+...+x^100)(1+x^25+x^50+x^75+x^100)(1+x^50+x^100)

multiplying this out would give me a 500th degree polynomial and the answer would be the coefficient of x^100 which i dont know how to get

tkhunny · Answer

Yeah, you don't want to do that. Try this: http://www.cut-the-knot.org/ctk/GeneratingFunctions.shtml It is not a simple task at all.

tkhunny · Answer

Of course, using my previuos idea of dividing from the 293 answer given in your original link, it should be immedaitely obvious that using dollars adds only one way to get $1.00.  Thus, 292.

anonymous · Answer

yea that is the answer, but i wanted to show my work instead of just putting the answer down and thanks for the link i take a look at it