Trouble Understanding AoPS Vol. $2$ Sequences/Series Proof From Chapter $16$ of The Art of Problem Solving, Volume $2$: and Beyond: 
Let $n$ be a positive integer and let $a_{n}$ denote the number of positive integers which can be formed whose digits are chosen from $\{1,3,4\}$ and the sum of whose digits are equal to $n$. Prove that $a_{2n}$ is a perfect square for every $n$.
The solution provided in the book claims that "It is fairly clear that $a_n=a_{n-1} + a_{n-3} + a_{n-4}$." I can't for the life of me see why this might be true, let alone prove it. Can anyone explain why this is?  
 A: The recurrence $a_n = a_{n - 1} + a_{n - 3} + a_{n - 4}$ results from a standard counting argument:
Definition: For convenience, call a positive integer $k_1k_2\cdots k_{s - 1}k_s$ to be of $\boxed{\textit{Type } n}$ if its digits $k_i$ come from $1, 3, 4$ and sum up to $n$.
Okay, so suppose $k_1k_2\cdots k_{s - 1}k_s$ is of Type $n$. Think of its last digit $k_s$. Since $k_s$ comes from $1, 3, 4$, there are three possibilities:


*

*$k_s = 1$: Then since $\sum\limits_{i = 1}^s k_i = n$, we have $\sum\limits_{i = 1}^{s - 1} k_i = n - k_s = n - 1$. That is, the remaining $s - 1$ digits $k_1k_2\cdots k_{s - 1}$ add up to $\boxed{n - 1}$.

*$k_s = 3$: Similarly in this case, the remaining $s - 1$ digits $k_1k_2\cdots k_{s - 1}$ must add up to $\boxed{n - 3}$.

*$k_s = 4$: And in this case, the remaining $s - 1$ digits $k_1k_2\cdots k_{s - 1}$ must add up to $\boxed{n - 4}$.


In other words, every positive integer $k_1k_2\cdots k_{s - 1}k_s$ of $\textit{Type } n$ is made up of


*

*either a positive integer of $\textit{Type } n - 1$ with $1$ concatenated at the end

*or a positive integer of $\textit{Type } n - 3$ with $3$ concatenated at the end

*or a positive integer of $\textit{Type } n - 4$ with $4$ concatenated at the end
And conversely. So as the three categories above are disjoint we get:
($\# \textit{ of Type } n$'s) $\ =\ $ ($\# \textit{ of Type } n - 1$'s) $\ +\ $ ($\# \textit{ of Type } n - 3$'s) $\ +\ $ ($\# \textit{ of Type } n - 4$'s) $\quad\text{i.e.}$
$$
a_n = a_{n - 1} + a_{n - 3} + a_{n - 4}
$$
