We will use generating functions to determine how many ways there are
to use pennies and nickels to give n cents change.
(i) Write the sequence Pn for the number of ways to use only pennies to
change n cents. Write the generating function for that sequence.
(ii) Write the sequence Nn for the number of ways to use only nickels to
change n cents. Write the generating function for that sequence.
(iii) Write the generating function for the number of ways to use pennies and
nickels to change n cents.
(iv) Write the generating function for the number of ways to use pennies,
nickels and dimes to change n cents.
the only thing i can think of so far is that pennies will have <1,1,1,1,1,…> 1+x+x^2+x^3+… and nickels will have <1,0,0,0,1,0,0,0,1,….> or something like that… don't know how to do the rest
Best Answer
For pennies you have the sequence $\langle 1,1,1,\dots\rangle$, which as you say correponds to the formal power series
$$1+x+x^2+\ldots=\sum_{n\ge 0}x^n\;.$$
That’s just a geometric series, so you know what the generating function is (even if you didn’t realize it right away:
$$\sum_{n\ge 0}x^n=\frac1{1-x}\;.$$
For nickels you can do almost the same thing. Your sequence is $\langle 1,0,0,0,0,1,0,\dots\rangle$, corresponding to another geometric series:
$$1+x^5+x^{10}+\ldots=\sum_{n\ge 0}x^{5n}=\sum_{n\ge 0}\left(x^5\right)^n=\frac1{1-x^5}\;.$$
For pennies and nickels you want
$$\left(1+x+x^2+\ldots\right)\left(1+x^5+x^{10}+\ldots\right)\;:\tag{1}$$
$(1)$ has one $x^n$ term for every way to write $n$ in the form $5m+k$ with $m,k\in\Bbb N$, which is precisely the number of ways to make the amount $n$ with nickels and pennies. Clearly, then, the generating function is just
$$\frac1{(1-x)(1-x^5)}\;.$$
I’ll leave the last part to you.