In how many ways can you withdraw $50\rm USD$ from an ATM using $1, 2, 5, 10$, and $20$ bills? The preferred method should not use a generating function.
I tried using just the create function, but my professor told me that's not how we're supposed to solve it, and now I'm stuck. I tried to use something like $$20x_1+10x_2+5x_3+2x_4+x_4=50$$ but in this case i can't proceed in my first attempt i used Generating function $$A(x)=\sum_{n=0}^\infty a_nx^n=\frac{1}{1-x},B(x)= \sum_{n=0}^\infty a_nx^{2n}=\frac{1}{1-x^2},C(x)= \sum_{n=0}^\infty a_nx^{5n}=\frac{1}{1-x^5} \ldots$$ then: $$\left\{ \begin{array}{c} S^a(x) =A(x)\\ (1-x^2)S^{AB}(x)=S^A(x) \\ (1-x^5)S^{ABC}(x)=S^A(x)\\ (1-x^{10})S^{ABCD}(x)=S^A(x)\\ (1-x^{20})S^{ABCDE}(x)=S^A(x)\\ \end{array} \right. $$ and i got to this point $$\left\{ \begin{array}{c} S^a_n=a_n=1\\ S^{AB}_n=S^A+S^{AB}_{n-2}\\ S^{ABC}_n=S^{AB}_N+S^{ABC}_{N-5}\\ S^{ABCD}_n=S^{ABC}+S^{ABCD}_{N-10}\\ S^{ABCDE}_n=S^{ABCD}+S^{ABCDE}_{N-20}\\ \end{array} \right. $$ but he said we don't have generating functions in our curriculum, and left me without any further informations. But we had them in Inhomogeneous recurrence. Now even I don't know About combinatorics in my syllabus:
Methods of counting combinatorial objects. Binary and polynomial coefficients. Combinatorial identities. The drawer principle. Basic principles and laws of conversion: the principle of bijection, the principle of addition and multiplication, and the principle of inclusions and exclusions.
We wish to figure out how many ways to draw $\$50$ from an ATM. The banknotes we have are $\$1$, $\$2$, $\$5$, $\$10$, and $\$20$.
Consider the series $$a_{n} = 1,1,1,1,1...$$ $$b_{n} = \begin{cases} 1 & n \equiv 1 \mod 2 \\ 0 & \text{otherwise} \end{cases}$$ $$c_{n} = \begin{cases} 1 & n \equiv 1 \mod 5 \\ 0 & \text{otherwise} \end{cases}$$ $$d_{n} = \begin{cases} 1 & n \equiv 1 \mod 10 \\ 0 & \text{otherwise} \end{cases}$$ $$e_{n} = \begin{cases} 1 & n \equiv 1 \mod 20 \\ 0 & \text{otherwise} \end{cases}$$
We can represent them as generating functions: $$A(x)=\sum_{n=0}^\infty a_{n}x^n=\frac{1}{1-x},B(x)= \sum_{n=0}^\infty b_{n}x^{2n}=\frac{1}{1-x^2},C(x)= \sum_{n=0}^\infty c_nx^{5n}=\frac{1}{1-x^5}, \text{etc.}$$ respectively.
Let's multiply $$S^{AB}(x)=A(x)B(x)$$ After multiplying we get: $$A(x)B(x) = (\sum_{n=0}^\infty a_nx^n) (\sum_{n=0}^\infty b_nx^{2n})= (1+x+x^2+x^3...)(1+x^2+x^4+x^6...)= 1+x+x^2+x^2+x^3+x^3+x^4+x^4+x^4+...$$
We cannot find the formula for this sequence, but we can extract some of its first elements $$2x^2, 2x^3, 3x^4...$$ $$S_n^{AB}=(1,1,2,2,3,3,4,4,5,5,...)$$
This series answers the question of how many ways can we form $n$ dollars using one and two dollar bills.
Since we could multiply two series together, why not multiply all of them? We'll get something like this: $$\left\{ \begin{array}{c} S^A(x) =A(x)\\ S^{AB}(x)=S^A(x)*B(x) \\ S^{ABC}(x)=S^{AB}(x)=C(x)\\ S^{ABCD}(x)=S^{ABC}(x)=D(x)\\ S^{ABCDE}(x)=S^{ABCD}(x)=E(x)\\ \end{array} \right.$$ Since these are ordinary geometric series, we can interpret them as: $$\left\{ \begin{array}{c} S^a(x) =A(x)\\ S^{AB}(x)=S^A(x)*\frac{1}{1-x^2}/(1-x^2) \\ S^{ABC}(x)=S^A(x)\frac{1}{1-x^5}/(1-x^5)\\ S^{ABCD}(x)=S^A(x)\frac{1}{1-x^{10}}/(1-x^{10})\\ S^{ABCDE}(x)=S^A(x)\frac{1}{1-x^{20}}/(1-x^{20})\\ \end{array} \right. $$ And we're left with something like this $$\left\{ \begin{array}{c} S^A(x) =A(x)\\ (1-x^2)S^{AB}(x)=S^A(x) \\ (1-x^5)S^{ABC}(x)=S^A(x)\\ (1-x^{10})S^{ABCD}(x)=S^A(x)\\ (1-x^{20})S^{ABCDE}(x)=S^A(x)\\ \end{array} \right. $$ $$$$ which after further transformations gives us: $$\left\{ \begin{array}{c} S^A_n=a_n=1\\ S^{AB}_n=S^A_n+S^{AB}_{n-2}\\ S^{ABC}_n=S^{AB}_n+S^{ABC}_{n-5}\\ S^{ABCD}_n=S^{ABC}_n+S^{ABCD}_{n-10}\\ S^{ABCDE}_n=S^{ABCD}_n+S^{ABCDE}_{n-20}\\ \end{array} \right. $$ And we can just use table to compute this: Table
I don't think this solution is very elegant, but it (I think) works.