Make $n$ cents with $1$-cent, $2$-cent, and $3$-cent coins 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$


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