# Number of ways to pay (generating functions)

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

• by NBS, isn't it: $(1-x)^{-2}=\sum_{n\ge 0} {-2\choose n} (-x)^n =\sum_{n\ge 0} {2+n-1\choose \color{red}{n}} x^n$? – farruhota Sep 14 '18 at 11:26

## 2 Answers

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

• How did you get the floor function? How to proceed with problem (2): $\frac12\left(\frac1{(1-x)^2}+\frac1{1-x^2}\right)\frac{1}{1-x^3} = \left(\sum_{k=0}^\infty\left\lfloor\frac{k+2}2\right\rfloor x^k\right) \cdot \left(\sum_{k=0}^\infty [\text{k is divisable by 3}] x^k\right)$, I'm not familiar with this kind of sums. – nik0la.vr Sep 14 '18 at 12:27
• @nik0la.vr: The remainder when $k$ is divided by $2$ is $k-2\left\lfloor\frac{k}2\right\rfloor$. We can write $[k\text{ is even}]$ as $1-\left(k-2\left\lfloor\frac{k}2\right\rfloor\right)=2\left\lfloor\frac{k+2}2\right\rfloor-k-1$. – robjohn Sep 14 '18 at 19:28
• @nik0la.vr: Another way to look at it is $\frac{k+1+[2\mid k]}2$ is an integer and if we add $1$ instead of $[2\mid k]$ it is at most $\frac12$ bigger than an integer, so taking the floor will give us the proper answer. – robjohn Sep 14 '18 at 23:33

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