How many ways to get a sum of 29 by adding 5 & 2? ex 5+5+5+5+5+2+2 = 29, is one way. Ex: $2+2+3$, $2+3+2$, $3+2+2$ these are three ways to get a sum of $7$ with $3$ and $2$. But my example is with $5$ and $2$ and a sum of $29$.
I believe there are three ways to get a sum of $29$ by using fives and nines. But is there any formula for this? What if I want to check the sum of $500$ or $1 000 0000$ using $5$ and $2$?
 A: Here's an observation: $(x^2+x^3)^k$ is a polynomial whose $x^n$ coefficient is the number of ways to get $n$ by using $k$ total $2$'s and $3$'s. So, if we don't care how many total we use, the $x^n$ coefficient of the geometric series
$$
\sum_{k=0}^\infty (x^2+x^3)^k = \frac{1}{1-x^2-x^3}
$$
is the number of ways of getting $n$ using any number of $2$'s and $3$'s.
The first terms of this are
$$
\frac{1}{1-x^2-x^3} = 1+x^2+x^3+x^4+2x^5+2x^6+3x^7+4x^8+5x^9+7x^{10}+\cdots.
$$
This supports what you found, that there are three ways to get $7$.
Getting a nice closed-form formula depends on factoring the denominator, if possible, to do partial fractions to represent this as a sum of geometric series. That's one way to calculate a particular coefficient. Another is to just go through with polynomial long division, which isn't so bad, but it will take a while to (by hand) figure out how many ways there are to get ten million!
For fives and nines, the corresponding rational function is
$$
\sum_{k=0}^\infty(x^5+x^9)^k = \frac{1}{1-x^5-x^9} = 1+x^5+x^9+x^{10}+2 x^{14}+x^{15}+x^{18}+3 x^{19}+x^{20}+3
   x^{23}+4 x^{24}+x^{25}+x^{27}+6 x^{28}+5
   x^{29} + \cdots.
$$
This says there are five ways of getting $29$, not three.
Another way to understand this, rather than using power series, is that to calculate the number of ways $f(n)$ of getting $n$ with fives and nines, you can calculate $f(n-5) + f(n-9)$ since you add together the number of ways where the last number chosen is a five and the number of ways where the last number chosen is a nine. Then you make a table starting with $n=0$ with $f(0)=1$ (since there is one way to get $0$). By calculating the values of this function at consecutive numbers, you get to reuse previous calculations. (This is equivalent to the long division approach.)
