<s>[INST] 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$

 [/INST] 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.
</s>