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)?

The generating function for problem $1$ is
$$
\begin{align}
\frac1{1-x}\frac1{1-x^2}
&=\frac12\frac1{1-x}\left(\frac1{1-x}+\frac1{1+x}\right)\\
&=\frac12\left(\color{#C00}{\frac1{(1-x)^2}}+\color{#090}{\frac1{1-x^2}}\right)\\
&=\sum_{k=0}^\infty\frac{\color{#C00}{k+1}+\color{#090}{[2\mid k]}}2\,x^k\\
&=\sum_{k=0}^\infty\left\lfloor\frac{k+2}2\right\rfloor x^k\tag1
\end{align}
$$
where $[\dots]$ are Iverson brackets.
The last step of $(1)$ is justified since $1-\frac{1+[2\mid k]}2=\frac{1-[2\mid k]}2\in[0,1)$.

The generating function for problem $2$ is
$$
\begin{align}
&\frac1{1-x}\frac1{1-x^2}\frac1{1-x^3}\\
&=\color{#C00}{\frac1{6(1-x)^3}}+\color{#090}{\frac1{4(1-x)^2}}+\color{#00F}{\frac1{4\!\left(1-x^2\right)}}+\color{#740}{\frac1{3\!\left(1-x^3\right)}}\\
&=\sum_{k=0}^\infty\left(\color{#C00}{\frac{(k+2)(k+1)}{12}}+\color{#090}{\frac{k+1}4}+\color{#00F}{\frac{[2\mid k]}4}+\color{#740}{\frac{[3\mid k]}3}\right)x^k\\
&=\sum_{k=0}^\infty\frac{(k+3)^2-4+3[2\mid k]+4[3\mid k]}{12}\,x^k\\
&=\sum_{k=0}^\infty\underbrace{\left\lfloor\frac{(k+3)^2}{12}+\frac12\right\rfloor}_\text{closest integer to $\frac{(k+3)^2}{12}$}\,x^k\tag2
\end{align}
$$
The last step of $(2)$ is justified since $\frac12-\frac{-4+3[2\mid k]+4[3\mid k]}{12}=\frac{10-3[2\mid k]-4[3\mid k]}{12}\in[0,1)$.
