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. 

 A: 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: 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$.
A: 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.
