5
$\begingroup$

I have a general question about numbers:

How many ways can we write $n$ as the sum of the numbers $1$,$2$ and $3$?

I know that we start with the following functions: $$\frac{1}{1-z} = 1+z+z^2+ \dots$$ $$\frac{1}{1-z^2} = 1+z^2+ z^4+ z^6 + \dots$$ $$\frac{1}{1-z^3} = 1+ z^3+ z^{6}+ z^{9} + \dots$$

Multiplying these together we get $$\sum C(n) z^n = \frac{1}{(1-z)(1-z^2)(1-z^3)}$$ where $C(n)$ is our answer. In other words, by multiplying out the polynomials and looking at the coefficients, I can verify that I get the answer. But how do I know that this gives me the answer? How would I get an explicit formula for $C(n)$? I think I have to do something with partial fractions. So $$\frac{1}{(1-z)(1-z^2)(1-z^3)} = \frac{A}{1-z} + \frac{B}{1-z^2}+ \frac{C}{1-z^3}$$ and we have to solve for $A$, $B$ and $C$?

6 Answers 6