<s>[INST] Number of ways to pay (generating functions) I've just started learning generating functions.


*

*Let $a_n$ be the number of ways in which you can pay $n$ dollars using 1 and 2 dollar bills. Find the generating function for $(a_0, a_1, a_2, \ldots)$ and general term $a_n$.

*Prove that the number of ways to pay $n$ dollars using only 1, 2, and 3 dollar bills is equal to closest integer of $\frac{(n+3)^2}{12}$?



What I've got so far: 
Let $f(x) = \frac{1}{1-x}$ be the generating function for $(1, 1, 1, ...)$. $1 + x^2 + x^4 + \ldots$ is the generating function for $(1, 0, 1, 0, 1, \ldots)$ which is equal to $f(x^2) = \frac{1}{1-x^2} = \frac{1}{(1-x)(1+x)}$.
$$
\begin{align}
& (1 + x + x^2 + \ldots)(1 + x^2 + x^4 + \ldots) \\
&= \frac{1}{(1+x)(1-x)^2} \\
&= \frac{1}{4} \cdot \frac{1}{1+x} + \frac{1}{4} \cdot \frac{1}{1-x} + \frac{1}{2} \cdot \frac{1}{(1-x)^2} \\
&= \frac{1}{4} \Sigma_{n \geq 0}{-1 \choose n}x^n + \frac{1}{4} \Sigma_{n \geq 0}x^n + \frac{1}{2} \Sigma_{n \geq 0}{2 + n - 1 \choose n}x^n \\
&= \Sigma_{n \geq 0}\Bigl((-1)^n \frac{1}{4} x^n + \frac{1}{4} x^n + \frac{1}{2}{n + 1 \choose n} x^n \Bigr) \\
&= \Sigma_{n \geq 0}\Bigl((-1)^n \frac{1}{4} x^n + \frac{1}{4} x^n + \frac{1 \cdot 2}{2 \cdot 2}(n + 1) x^n \Bigr) \\
&= \Sigma_{n \geq 0} \frac{1}{4} \Bigl((-1)^n x^n + x^n + 2(n + 1) x^n \Bigr)
\end{align}
$$
I don't know is this is correct nor how to proceed.

I guest that we use similar method to solve problem (2)?
 [/INST] we have with $n_1$ 1 dollar bills and $n_2$ 2 dollar bills we have: $n_1+2n_2 = n$. which has a solution for every $n_1$ such that $n-n_1$ is even.
So if $n$ is odd then there are $(n+1)/2$ possible ways of paying.
So if $n$ is even then there are $(n/2)+1$ possible ways of paying.
Hence problem 1 is done.
Let the solution to problem 1) be $a_n$.
So for the problem 2) we have $n_1+2n_2+3n_3 = n$. 
Let the solutions to problem 2) be $b_n$.
Then we have $b_n = \sum_{i,3 | (n-i)} a_i$.
</s>