Trouble Understanding AoPS Vol. $2$ Sequences/Series Proof

Question

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?

Answer 1

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} $$