Thread: Generating Function help

Hey there I need some help on what to do next for this problem.

In 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^15+....+x^100) <- nickels
(1+x^10+x^20+x^30+...+x^100) <- dimes
(1+x^25+x^50+x^75+x^100) <- quarters
(1+x^50+x^75+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 do I do from here to get the answer I need?

Hey gfbrd.

What does this function refer to? Are you trying to solve a recurrence relation? Is this function meant to be equal to 0 where you need to find the roots?

sorry but i dont think i did anything wrong here, all i want to know is how do i get the coefficient for x^100 from the generating function

Ohh I see what you are trying to do.

Try expanding out (1-x^5)(1-x^10)(1-x^25)(1-x^50) and then look at the generating function for (1-x) when you get these terms multiplied by the expansion to give x^100 (there should be 16 terms to look for) then collect the coeffecients together.

what do you mean by expanding?
do I multiply this out?

(1+x+x^2+x^3+...+x^100)(1+x^5+x^10+x^15+....+x^100 )(1+x^10+x^20+x^30+...+x^100)(1+x^25+x^50+x^75+x^1 00)(1+x^50+x^75+x^100)
if so how do I multiply this out, it would take forever to do it by hand

No don't do that: multiply out (1-x^5)(1-x^10)(1-x^25)(1-x^50) and then look for when x^n * all the individual terms in the expanding polynomial give an x^100 term and collect those terms together.

Your generating function will be in terms of a_n*x^n so all you need to check are the terms where a_n*x^n * blah*x^k give a_n*blah*x^(n+k) where n+k = 100.

ok i expanded it and i got

1-x^5-x^10+x^15-x^25+x^30+x^35+x^40-x^50+x^55+x^60-x^65+x^75-x^80-x^85+x^90

i dont really see any x^100 terms here
im not sure what do i really do next sorry im a bit slow on this

Now you have to consider (1-x^5-x^10+x^15-x^25+x^30+x^35+x^40-x^50+x^55+x^60-x^65+x^75-x^80-x^85+x^90)*a_n*x^n where all these terms have a x^100 term in them.

For example 1*a_n*x^n has n = 100, while -x^5*a_n*x^n has n = 95 and so on.

going from left to right i get n=100,n=95,n=90,n=85,n=75,n=70,n=65,n=60,n=50,n=45 ,n=40,n=35,n=25,n=20,n=15,n=10
but what do i do with these terms though? sorry i need to take this slowly to understand

Now you need to consider what the a_n's are for those terms and then add them up.

Remember that these terms are the only time the whole series if were expanding out as a generating function gave a b_n*x^n where n = 100 where this is for the full expanding series.

Since you have all the possible terms where the n = 100 for the b_n, then the b_n for the expanding series will be the same of all the a_n's in your 1/(1-x) that correspond to those terms which means if you find all the a_n's and multiply them by the coffecients in the polynomial you just expanded then you will get the b_100 term which is the coffecient of the generating series for n = 100.

A few examples might clear things up:

1*a_100 for the first term
-a_5 for the second term
-a_10 for the third term

and so on

and then the final coffecient will be the sum of all these terms since all these terms have the common x^100 term if you looked at the completely expanding generator function with x^100*b_100 (you are trying to find b_100).

sorry i dont know if i understand this or not
1a_100-a_95-a_90+a_85-a_75+a_70+a_65+a_60-a_50+a_45+a_40-a_35+a_25-a_20-a_15+a_10

That's the right technique and that should give you the coeffecient for the 100th term if the polynomial and the calculation is correct.

so its a_120? if so then i think there might be a mistake, because i believe the answer should be 292 istead

No it's not that: you don't add up the indexes but the actual values.

a_100 is the value of the generating series of 1/(1-x) at the 100th position, a_75 is at the 75th position (i.e. n = 100. n = 75) and so on. You need to add these terms up, not the indices themselves.

Oh alright thanks for all your help