Make $n$ cents with $1$-cent, $2$-cent, and $3$-cent coins

Question

I encountered the following problem in Herber Wilf's book Generatingfunctionology:

Prove that, in country that has $1$-cent, $2$-cent, and $3$-cent coins only, the number of ways of changing $n$ cents is exactly the integer nearest to $ \frac{(n+3)^2}{12} $.

Of course, the solution provided was one that makes use of a generating function. However, it is unbelievably tedious. Is there a way to do this without making use of a generation function?

---

For reference, here is the solution given in the book.

If $f(n)$ is that number, then $$ \begin {gather*} \sum_{n\ge 0} f(n) x^n = \frac {1}{(1-x)(1-x^2)(1-x^3)}\qquad\qquad\qquad\qquad \\ = \frac{1}{6(1-x)^3} + \frac{1 }{4(1-x)^2} + \frac {17}{72(1-x)} + \frac {1}{8(1+x)} + \frac {1}{9(1-\omega x)} + \frac {1}{9(1-\overline{\omega}x)}. \end {gather*} $$ If we expand each of the fractions on the right, we find the formula $$ f(n) = \frac {1}{6} \dbinom {n+2}{2} + \frac {1}{4} (n+1) + \frac {17}{72} + \frac {(-1)^n}{8} + \frac {2}{9} \cos \left( \frac {2n \pi}{3} \right), $$ which can be rewritten as $$ f(n) = \frac {(n+3)^2}{12} + \frac {-7 + 9 (-1)^n + 16 \cos \left( \frac {2n\pi}{3} \right)}{72}. $$ The second fraction cannot exceed $ \frac {32}{72} < \frac {1}{2} $ in absolute value, so $f(n)$ is the unique integer who distance from $ \frac {(n+3)^2}{12} $ is less than $\frac{1}{2}$, as required. $\Box$

Answer 1

The following method could be explained to any student that understands equations for lines and knows how to sum an arithmetic sequence. However, you may find it at least as tedious as the method you already have!

The Idea

Think of points $(x,y)$ in the plane as representing "$x$ 2-cent coins and $y$ 3-cent coins".   Now, the grid points in the first quadrant on or below the line $\mathcal L_N$ given by $$2x+3y=N$$ are in one-to-one correspondence with ways of changing $N$ cents.

Since the area of this triangular region is $\frac 12\frac N2 \frac N3=\frac{N^2}{12}$, we can already see that the number of points should be on the order of $\frac{N^2}{12}$. So far, so good.

An Exact Calculation

To find the exact number of points, we will consider the number $k_N$ of first-quadrant points that lie on $\mathcal L_N$, for each value of $N$.   (Yes, we are taking the first quadrant to include its boundary.)   Since every grid point $(x,y)$ lies on some $\mathcal L_N$ (namely $\mathcal L_{2x+3y}$), the total number $A_N$ of first quadrant grid points on or below $\mathcal L_N$ is given by $A_N = \sum_{n=0}^{N} \mathcal k_n$.

We can see that each $\mathcal L_N$ meets grid points at regular intervals, namely with an inter-point spacing of $\overrightarrow{(3,-2)}$.   Since this is exactly the amount by which the first-quadrant portion of $\mathcal L_N$ lengthens when $N$ increases by $6$, and each grid point on $\mathcal L_N$ is both directly below (by $2$ units) and directly to the left of (by $3$ units) a grid point on $\mathcal L_{N+6}$, we see that $k_{n+6}=k_n+1$.   Thus it suffices to find $k_0$ through $k_5$, and by inspection we see that they are all equal to $1$ except for $k_1$ which is $0$.

$$\begin{eqnarray}(k_0,k_1,k_2,\ldots) = & 1,0,1,1,1,1, \\ & 2,1,2,2,2,2, \\ & 3,2,3,3,3,3, \\ & etc. \end{eqnarray}$$

This regularity allows us to find exact formulas for $A_N$ depending on $N$ mod $6$.

$$\begin{eqnarray} (A_0,\ A_6,\ A_{12},\ \ldots) &=& (1,\ 1+6,\ 1+6+12,\ \ldots) & \\ \mbox{So }\ \ \ \ A_{n=0+6m} &=& 1+6m(m+1)/2 &=& (n^2+6n+12)\;/\;12 \\ \mbox{Similarly, }\ \ \ \ A_{n=1+6m} &=& 1+6m(m+1)/2+m &=& (n^2+6n+5)\;/\;12 \\ A_{n=2+6m} &=& 1+6m(m+1)/2+2m+1 &=& (n^2+6n+8)\;/\;12 \\ A_{n=3+6m} &=& 1+6m(m+1)/2+3m+2 &=& (n^2+6n+9)\;/\;12 \\ A_{n=4+6m} &=& 1+6m(m+1)/2+4m+3 &=& (n^2+6n+8)\;/\;12 \\ A_{n=5+6m} &=& 1+6m(m+1)/2+5m+4 &=& (n^2+6n+5)\;/\;12 \\ \end{eqnarray}$$

We can see that this is always within $\left[\,\frac{\!\!-4}{12}, \frac{3}{12}\right]$ of $(n+3)^2\,/\,12$.

This means that $A_n$ is always the integer nearest to $(n+3)^2\,/\,12$.

Answer 2

I'll only show how to obtain a linear recurrent relation from the problem, it has been explained at various places how to solve these.

Let:

• $a(n)$ be solutions (ways how to change $n$) using only $1$c,
• $b(n)$ solutions using only $1,2$c and at least one $2$c,
• $c(n)$ solutions using all three coins and at least one $3$c.

Clearly each solution fits exactly into one of the 3 categories, therefore $f(n)=a(n)+b(n)+c(n)$.

We have $a(n)=1$. For $b(n)$, we remove one $2$c, and either we get something with another $2$c left or not. Therefore $b(n)=b(n-2)+a(n-2)$. Similarly $c(n)=c(n-3)+b(n-3)+a(n-3)$. Of course, this works only for $n>3$, so we have to add that $a(1)=a(2)=a(3)=b(2)=b(3)=c(3)=1$ and $b(1)=c(1)=c(2)=0$. This linear recurrence should have the desired solution.

However, as you see, it's much simpler to just use OGF for this kind of problems.

Answer 3

It is possible to shorten a bit the argument by noticing that $$\operatorname{Res}\left(\frac{1}{(1-z)(1-z^2)(1-z^3)},z=1\right)=-\frac{17}{72},$$ hence the contribute given by the simple poles $-1,\omega,\omega^2$ lying on the unit circle cannot exceed $\frac{17}{72}$, and is exactly equal to $\frac{17}{72}$ when $6\mid n$. The pole in $z=1$ is a triple pole, hence $f(n)$ grows like a second-degree polynomial. By interpolating the values of $f(n)$ on $n=0,n=6,n=12$ we can derive our formula.

Answer 4

This is a solution form the book ''CHALLENGING MATHEMATICAL PROOLEMS WITH ELEMENTARY SOLUTIONS VOL 1'' by A. M. Yaglom and I. M. Yaglom :

In making up $n$ cents out of 1-, 2-, and 3-cent stamps, we can use either no 3-cent stamps at all, or one 3-cent stamp, or 2 of them, etc., up to a maximum of $q = \left[n/3\right]$ of them. In the first case the $n$ cents would have to be made up entirely out of 1- and 2-cent stamps, which can be done in $\left[n/2\right] + 1$ ways (Please see the notes). In the second case we must form $n-3$ cents with 1- and 2-cent stamps, which can be done in $\left[(n-3)/2\right] + l$ ways. In the third case we must form $n-6$ cents, which can be done in $\left[(n-6)/2\right] + 1$ ways. In general, in the $(k+1)^{th}$ case, we must form $n-3k$ cents with 1- and 2-cent stamps, which can be done in $\left[(n-3k)/2\right] + l$ ways.

Let $n = 3q + r$, where $q = \left[n/3\right]$ is the quotient obtained by dividing 3 into $n$, and $r$ is the remainder (thus $r = 0, l$, or $2$). We then see that in the final case (where $q$ 3-cent stamps are used), the remaining $r$ cents must be made up out of 1- and 2-cent stamps. This can be done in $[r/2] + 1$ ways, so we get a total of $$ S = \left(\left[\frac{n}{2}+1 \right] \right) + \left(\left[\frac{n-3}{2}+1 \right] \right) + \left(\left[\frac{n-6}{2}+1 \right] \right) + \ldots +\left(\left[\frac{r}{2}+1 \right] \right) $$ Now, we note that for any integer $m$, $\left[\frac{m}{2} \right] = \frac{m}{2} - \frac{1}{4} + \frac{(-1)^m}{4}$. We use this fact to simply the expression for $S$. $$ \begin{aligned} S = & \left(\frac{n}{2}+\frac{3}{4}+\frac{(-1)^{n}}{4} \right) + \left(\frac{n-3}{2}+\frac{3}{4}+\frac{(-1)^{n-3}}{} \right) \\ + & \left(\frac{n-6}{2}+\frac{3}{4}+\frac{(-1)^{n-6}}{4} \right) + \ldots + \left(\frac{r}{2}+\frac{3}{4}+\frac{(-1)^{r}}{4} \right) \end{aligned} $$ Since there are $q + 1$ parentheses each containing a $\frac{3}{4}$, we have $$ \begin{aligned} S = & \frac{3(q+1)}{4} + \left( \frac{(-1)^n}{2}+\frac{(-1)^{n-3}}{2}+\frac{(-1)^{n-6}}{2}+\ldots+\frac{(-1)^r}{2} \right) \\ + & \left(\frac{n}{2}+\frac{n-3}{2}+\frac{n-6}{2}+\ldots+\frac{r}{2} \right) \end{aligned} $$ The terms in the first parenthesis alternate in sign. Therefore this parenthesis is equal to $\frac{1}{4}$ if both $n$ and $r$ are even, $\frac{-1}{4}$ if both are odd, and $0$ otherwise. We will denote its value by $\epsilon$, and note for later purposes that $\epsilon \geq 0$ when $r$ is even. The terms of the second parenthesis are in arithmetic progression. So, $$ \begin{aligned} S & = \frac{3(q+1)}{4} + \epsilon + \frac{q+1}{2}\left(\frac{n}{2}+\frac{r}{2} \right) \\ & = \frac{q+1}{4} \left( 3+n+r \right) + \epsilon \\ & = \frac{3q+3}{12} \left( 3+n+r \right) + \epsilon \\ & = \frac{(n+3+r)(n+3-r)}{12} + \epsilon \\ & = \frac{\left(n+3) \right)^2}{12} - \frac{r^2}{12} + \epsilon \end{aligned} $$ The rest is to show that $\left| - \frac{r^2}{12} + \epsilon \right| \leq \frac{1}{2}$ for $r=0, 1, 2$. Thus $S$, which is an integer, differs from $(n +3)^2/12$ by a quantity whose absolute values is less than $\frac{1}{2}$· Therefore $S$ is the integer nearest to $(n+3)^2/12$.

Note : Please see the problem 22 of the same book about an argument that to make $n$ cents with only pennies and another coin having the value of $k$ cents, then the number of ways would be $\left[\frac{n}{k}\right]+1$ .