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$


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