How many different ways can a number be written as a sum of 1, 3, and 5? I had a programming question where we had to write code to output, given some number x, all the different ways x can be written as a sum of 1, 3 and 5. So for instance if x=6, then the answer is 4, as x=5+1=3+3=3+1+1+1=1+1+1+1+1+1.
This made me wonder how the same question could be done without using a computer, but I was unsure how one would go about doing this. Please try and explain how this could be done, preferably in the simplest way possible.
 A: The generating function approach is to note that if you write:
$$\begin{align}
f(x)&=\frac{1}{1-x}\frac{1}{1-x^3}\frac{1}{1-x^5}\\
&=(1+x+x^2+x^3+\cdots)(1+x^3+x^6+x^9+\cdots)(1+x^5+x^{10}+\cdots)\\
&=a_0+a_1x+a_2x^2+\cdots
\end{align}$$
Then $a_n$ counts the number of ways to partition $n$ into values in $1,3,5.$
Then we use the method of partial fractions to write:
$$f(x)=\frac{a}{(1-x)^3}+ \frac{b}{(1-x)^2}+\frac{c}{1-x}+ \frac{dx+e}{1+x+x^2}+\frac{fx^3+gx^2+hx+j}{1+x+x^2+x^3+x^4}$$
You can solve for $a,b,c,d,e,f,g,h,j$.
This is tedious, but you really only need to compute $a,b,c$, and there are tricks for doing so. Then you'll get a formula $c\binom{n+2}{2}+b\binom{n+1}{2}+a\binom{n}{2}$. As noted in comments, $a_n-\left(c\binom{n+2}{2}+b\binom{n+1}{2}+a\binom{n}{2}\right)$ will be periodic of period $15$, so you only have to figure out $a_0,\dots,a_{14}$  to figure out what the "correction" is.
I used Wolfram Alpha to find a,b,c.
It turns out the closed formula is the nearest integer to $\frac{(n+4)(n+5)}{30}=\frac{1}{15}\binom{n+5}{2}$.
I've checked this answer against Marcus's (now-deleted) answer, and it works up to $n=10000$, so I'm pretty sure my arithmetic was accurate.
A: A bit uncertain if it is worth carrying out the calculations, but anyway: As suggested by Did (and Thomas) the generating function seems a reasonable approach. In order to get a palpable result you may want to use a factorization by noting that $(1-t)(1-t^3)(1-t^5)$ is a divisor of $(1-t^{15})(1-t)(1-t)$ (follows from looking at roots). Carrying out the polynomial division you arrive at a fairly nice looking formula:
$$ f(t)=\frac{1}{(1-t)(1-t^3)(1-t^5)}= \frac{1-t+t^3-t^4+t^5-t^7+t^8}{(1-t^{15})(1-t)^2}$$
Writing $q(t)=1-t+t^3-t^4+t^5-t^7+t^8=q_0+q_1 t+\cdots+q_8 t^8$ 
and expanding the denominator in power-series:
$$ f(t) = q(t)(1+t^{15}+t^{30}+...) (1+2t+3t^2+4t^3+...) $$
One may further note that (quite magically by the way, probably for some underlying reason, from the 7th term it is completely regular?):
$$ Q(t)=q(t)(1+2t+3t^2+4t^3+...) = 1+t+t^2+2t^3+t^4+t^5+t^6+\sum_{k\geq 0} kt^{k+3}$$ So we arrive at
$$ f(t) = (1+t+t^2+2t^3+t^4+t^5+t^6)(1+t^{15}+t^{30}+..) + R(t).$$
The first term is 15-periodic and
$$ R(t) = \sum_{k\geq 1} \sum_{j\geq 0} k \; t^{k+15 j+3} = 
\sum_{n\geq 4} \sum_{j=0}^{j^*}  (n-3-15j)  \; t^{n} =
\sum_{n\geq 4} r_n t^n $$
with $r_n= (j^*+1)(n-3-\frac{15 j^*}{2})$ and $j^*=\lfloor\frac{n-3}{15} \rfloor$.
gives the increasing part.  (But I see that Thomas has got a nice 'explicit' and simple formula)
