Number of ways to pay (generating functions)

Question

I've just started learning generating functions.

1. 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$.
2. 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)?

Answer 1

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)$.

Answer 2

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$.