Prove that $a_n$ is a perfect square if $n$ is even without generating functions or Taylor series.

Let $a_n$ be the number of positive integers whose digits are all $1$, $3$, or $4$, and add up to $n$.

For example, $a_5 = 6$, since there are six integers with the desired property: $41, 14, 311, 131, 113$, and $11111$.

Prove that $a_n$ is a perfect square if $n$ is even.

I did some experimentation with small cases and found the recurrence relation $a_n=a_{n-1}+a_{n-3}+a_{n-4}$. How should I continue?

Also, I'd prefer a solution that does not use generating functions or the Taylor series.

Solution 1:

It's easy to observe numerically that $a_{2n} = F_n^2$, where $F_n$ is the $n$th Fibonacci number. That motivates looking for a bijection between the integers counted by $a_n$ and ordered pairs of Fibonacci numbers.

It's also well-known that $F_n$ counts partitions of an $n\times 1$ rectangle into $1\times1$ squares and $2\times1$ rectangles. For example, $F_4=5$ because:

So $F_n^2$ counts partitions of an $n\times2$ rectangle into the same pieces. For example, $F_3^2=9$ because:

For each such diagram, draw a zigzag line starting from upper left, going S then NE then S then NE ... until ending at the bottom right:

Now break the zigzag into pieces as much as possible while having each $2\times1$ rectangle lie all in the same piece:

Finally, reading the lengths of the pieces in order along each zigzag results in the integers counted by $a_n$:

$\displaystyle \begin{matrix} 111111&1113&1311\\1131&114&141\\3111&33&411 \end{matrix}$