# 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.

-
From that recurrence one can find a closed form of a_n. –  Assaultous2 Aug 22 '14 at 22:23
–  Semiclassical Aug 22 '14 at 22:25
yeah, that's pretty much this question, but is there a solution without generating functions and taylor series? edit: thanks MJD –  heyhuehei Aug 22 '14 at 22:28
Then can you add that specifically to your question? "Prove this without generating functions" isn't a duplicate, but "Prove this" is. –  Semiclassical Aug 22 '14 at 22:36
ok I fixed it :) –  heyhuehei Aug 22 '14 at 22:37

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

-
Another way of seeing this same bijection: $F_n$ counts the number of length-$n$ bit strings starting with $0$ with no two consecutive $1$s (the $1$s mark the ends of the $1\times2$ squares); similarly, $a_{2n}$ counts the number of length-$2n$ bit strings starting with $0$ where the $1$s come in runs of exactly $2$ or $3$. Given ordered pairs of the former, interlace them and then place an additional $1$ in front of each existing $1$ (if there's a $1$ already there, don't change it). This is a bijection. Example in next comment: –  Greg Martin Aug 23 '14 at 14:38
For $n=3$, the ordered pairs $(000,000)$, $(000,001)$, $(000,010)$, $(001,000)$, $(001,001)$, $(001,010)$, $(010,000)$, $(010,001)$, and $(010,010)$ interlace to $000000$, $000001$, $000100$, $000010$, $000011$, $000110$, $001000$, $001001$, and $001100$, which after adding the extra $1$s become, respectively, $000000$, $000011$, $001100$, $000110$, $000111$, $001110$, $011000$, $011011$, and $011100$. This is the same bijection as above; the examples are listed in the same order even. –  Greg Martin Aug 23 '14 at 14:44