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