# The number of positive integers whose digits are all $1$, $3$, or $4$, and add up to $2k$, is a perfect square

I have been stuck on this question for a pretty long time. My teacher says that we should find a small pattern, but I can't find one. Can anyone give me a hand?

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

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

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

• oeis.org/A006498 – Belgi Aug 21 '14 at 0:48
• Looking at a few of the even cases, it looks to be a bit more specific: $b_{2n}=f_n^2$ where $f_n$ is the $n$-th Fibonacci number... – Semiclassical Aug 21 '14 at 0:57

First note that since $F_n=F_{n-1}+F_{n-2}$, we have \begin{align} F_n^2 &=F_{n-1}^2+F_{n-2}^2+2F_{n-1}F_{n-2}\\ &=2F_{n-1}^2+2F_{n-2}^2-(F_{n-1}-F_{n-2})^2\\ &=2F_{n-1}^2+2F_{n-2}^2-F_{n-3}^2\tag{1} \end{align} a recursion for the squares of the Fibonacci numbers.

The generating function for the count of numbers whose digits are $1$, $3$, or $4$, and whose digits sum to $n$ is $$\frac1{1-x-x^3-x^4}=\sum_{k=0}^\infty\left(x+x^3+x^4\right)^k\tag{2}$$ To examine the coefficients of the even powers of $x$, we compute the even part of $(2)$: \begin{align} \frac12\left(\frac1{1-x-x^3-x^4}+\frac1{1+x+x^3-x^4}\right) &=\frac{1-x^4}{1-x^2-4x^4-x^6+x^8}\\ &=\frac{1-x^2}{1-2x^2-2x^4+x^6}\tag{3} \end{align} Since the denominator of $(3)$ is $1-2x^2-2x^4+x^6$, the coefficients of $x^{2n}$ in $(3)$ satisfy the recursion $a_n=2a_{n-1}+2a_{n-2}-a_{n-3}$, which is recursion $(1)$, satisfied by the squares of the Fibonacci numbers.

Computing the beginning of the Taylor series for $(3)$, we get $$\frac{1-x^2}{1-2x^2-2x^4+x^6}=1+x^2+4x^4+9x^6+\dots\tag{4}$$ and since the coefficients satisfy $(1)$, they are the squares of the Fibonacci numbers.

A direction (I leave it to you to see where this goes) : We can prove that $$b_{n}=b_{n-1}+b_{n-3}+b_{n-4}$$

with initial values given by $$b(1)=1,\, b(2)=1,\, b(3)=2,\, b(4)=4$$

We can see this is true since we can generate a sequence that adds to $n$ with a sequence that adds to $n-1$ with adding $1$to be the rightmost number in the sequence (and similarly with $b_{n-3},b_{n-4})$, you can convince yourself that this way avoids repetitions in counting.

Since this is a linear recursion we can solve it: Note that $i$ is a root of the characteristic polynomial $$p(x)=x^{4}-x^{3}-x-1$$

and thus so is $-i$ and using polynomial division we are left with a quadratic which roots are real and easy to find using the quadratic formula. This should at least give you a formula for $b_{n}$. You can then try to see if setting $b_{2n}$ in the formula you can write it as a square. It might be worth noting that in the expression for $b_{n}$ you will have a sum with $$a(i)^{n}+b(-i)^{n}$$

where $a,b$ will be known using the initial conditions and $i^{n}=(-i)^{n}=1$ when $n$ is even and so this will reduce to $a+b$.

Hi I have found the pattern, and I hope it helps.

By just listing out the value of $b_n$, $b_2$=1=$1^2$, $b_4$=4=$2^2$, $b_6$=9=$3^2$, $b_8$=25=$5^2$, $b_{10}$=64=$8^2$, $b_{12}$=169=$13^2$, $b_{14}$=441=$21^2$...... We can see that the numbers under the power are Fibonacci numbers.

• This is described in the oeis link along with other descriptions (as well as in the other comment) – Belgi Aug 21 '14 at 1:23