Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
From that recurrence one can find a closed form of a_n. –  Assaultous2 Aug 22 at 22:23
    
    
yeah, that's pretty much this question, but is there a solution without generating functions and taylor series? edit: thanks MJD –  heyhuehei Aug 22 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 at 22:36
    
ok I fixed it :) –  heyhuehei Aug 22 at 22:37

1 Answer 1

up vote 3 down vote accepted

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:

F_5

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

F_3^2

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:

F_3^2 with zigzags

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

breaking up those zigzags

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

share|improve this answer
    
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 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 at 14:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.