A currency called a mathik has only 1, 3, and 6 mathik bills. How many ways can one pay 300 mathiks? I have an idea on how to solve it, but there are too many ways for substitution. Do I use recursion?
For avoidance of doubt, paying 297 1-mathik bills and then a 3-mathik one is the same as paying a 3-mathik bill and then 297 1-mathik bills.
 A: The fact that there are only the three denominations $1,$ $3,$ and $6,$
where $1$ divides $3$ and $3$ divides $6,$ helps keep things less complicated than they might have been.
To avoid counting the same way of paying the bill twice, you could pay the six-mathik bills first, then the three-mathik bills, then the one-mathik bills.
You could solve the problem by recursion. I'd recommend only dealing with total debts that are divisible by $6,$ and keeping track not only of how many ways you can pay each with just six-, three-, and one-mathik bills but also how many ways you can pay using just three-mathik and one-mathik bills.
The number of ways you can pay $6(n+1)$ mathiks then is the number of ways
you can pay the first $6$ mathiks with a six-mathik bill and the remaining $6n$ mathiks using any combination of bills,
plus the number of ways you can pay the first $6$ mathiks with $2$ three-mathik bills and the remaining $6n$ mathiks using any combination of three-mathik and one-mathik bills, plus one way in which you pay the entire debt with $6(n+1)$ one-mathik bills.

Here's another approach:
The greatest number of six-mathik bills one can use when paying $300$ matiks is $50$ bills.
There is only one way to pay the bill while using $50$ six-mathik bills.
$$50\times6=300.$$
You can also pay using exactly $49$ six-mathik bills and some other bills.
There are exactly three ways to do this:
\begin{align}
49 \times 6 + 2\times3 = 300,\\
49 \times 6 + 1\times3 + 3\times1= 300,\\
49 \times 6 + 6\times1 = 300.\\
\end{align}
There are exactly five ways to pay while using exactly $48$ six-mathik bills:
\begin{align}
48\times 6 + 4\times3 = 300,\\
48\times 6 + 3\times3 + 3\times1= 300,\\
48\times 6 + 2\times3 + 6\times1= 300,\\
48\times 6 + 1\times3 + 9\times1= 300,\\
48\times 6 + 12\times1 = 300.\\
\end{align}
Do you see a pattern? Can you find the answer now?
A: $\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

In dealing with constraints, Iverson Brackets are quite useful . Namely,

\begin{align}
&\bbox[#ffe,10px]{\ds{\sum_{a_{1} = 0}^{\infty}
\sum_{a_{3} = 0}^{\infty}\sum_{a_{6} = 0}^{\infty}
\bracks{a_{1} + 3a_{3} + 6a_{6} = 300}}} =
\sum_{a_{6} = 0}^{\infty}\sum_{a_{3} = 0}^{\infty}\sum_{a_{1} = 0}^{\infty}
\bracks{a_{1} = 300 - 3a_{3} + 6a_{6}}
\\[5mm] = &\
\sum_{a_{6} = 0}^{\infty}\sum_{a_{3} = 0}^{\infty}
\bracks{300 - 3a_{3} + 6a_{6} \geq 0} =
\sum_{a_{6} = 0}^{\infty}\sum_{a_{3} = 0}^{\infty}
\bracks{a_{3} \leq 100 - 2a_{6}}
\\[5mm] = &\
\sum_{a_{6} = 0}^{\infty}\bracks{100 - 2a_{6} \geq 0}
\sum_{a_{3} = 0}^{100 - 2a_{6}}1 =
\sum_{a_{6} = 0}^{\infty}\bracks{a_{6} \leq 50}\pars{101 - 2a_{6}} =
101\sum_{a_{6} = 0}^{50}1 - 2\sum_{a_{6} = 0}^{50}a_{6}
\\[5mm] = &\
101 \times 51 - 2\,{50 \times 51 \over 2} = \bbx{2601}
\end{align}
A: The following holds:


*

*The number $ \color{blue}{j}$ of $6$ mathik bills we can use is $0\leq j \leq \frac{300}{6}=50$.

*Since then $300-6j$ mathiks are left, the number $\color{blue}{k}$ of $3$ mathik bills we can use is $$0\leq k\leq\frac{300-6j}{3}=100-2j$$

*The rest is left for $1$ mathik bills.

We conclude the number of possibilities is
  \begin{align*}
\sum_{\color{blue}{j}=0}^{50}\sum_{\color{blue}{k}=0}^{100-2j}1&=\sum_{j=0}^{50}(101-2j)\\
&=51\cdot 101-2\cdot\frac{50\cdot 51}{2}\\
&=51^2\\
&=\color{blue}{2601}
\end{align*}

A: The coefficient on $x^{300}$ in the following polynomial:
$$
\left(\sum_{k=0}^{300}x^k\right)
\left(\sum_{k=0}^{100}x^{3k}\right)
\left(\sum_{k=0}^{50}x^{6k}\right)
$$
which is $2601$ according to Maple.
A: If you look at the problem in general, that is, replace $300$ with $n$, you can let the number of ways be $a(n)$. By looking at the first few values of $a(n)$ you will see that each value repeats three times. That is, let $b(n)=a(3n)$, then $a(n)=b(\lfloor n/3\rfloor)$. By searching in OEIS, http://oeis.org/A002620 you will find that the sequence $b(n)$ is the sequence of quarter-squares with a different offset. See more details in the OEIS link. In your case the answer is $\lfloor(300/3+2)^2/4\rfloor=2601$.
