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. 


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.
