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

  • 1
    $\begingroup$ 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$? $\endgroup$ – farruhota Sep 14 '18 at 11:26

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

  • $\begingroup$ 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. $\endgroup$ – nik0la.vr Sep 14 '18 at 12:27
  • $\begingroup$ @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$. $\endgroup$ – robjohn Sep 14 '18 at 19:28
  • $\begingroup$ @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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.