Problem 1098

Let $N=\overline{x_{1} x_{2} \cdots x_{k}}$, where $x_{1}, x_{2}, \cdots, x_{k} \in\{1,3,4\}$, and $x_{1}+x_{2}+\cdots+x_{k}=n$. Assuming $n>4$, when $x_{1}$ is removed, then when $x_{1}$ takes $1,3,4$ respectively, $x_{2}+x_{3}+\cdots+x_{k}$ equals $n-1, n-3, n-4$, hence when $n>4$, $a_{n}=a_{n-1}+a_{n-3}+a_{n-4}$, and it is easy to see that $a_{1}=1, a_{2}=1, a_{3}=2, a_{4}=4$.
(1) is a 4th-order difference equation, whose characteristic equation $x^{4}-x^{3}-x-1=0$ has four roots $\pm \mathrm{i}, \frac{1}{2}(1 \pm \sqrt{5})$. Therefore, the solution to (1) is $a_{n}=C_{1} \mathrm{i}^{n}+C_{2}(-\mathrm{i})^{n}+C_{3}\left(\frac{1+\sqrt{5}}{2}\right)^{n}+C_{4}\left(\frac{1-\sqrt{5}}{2}\right)^{n}$, using the initial values (2) we get $a_{n}=\frac{2-\mathrm{i}}{10} \cdot \mathrm{i}^{n}+\frac{2+\mathrm{i}}{10}(-\mathrm{i})^{n}+\frac{1}{5}\left(\frac{1+\sqrt{5}}{2}\right)^{n+2}+\frac{1}{5}\left(\frac{1-\sqrt{5}}{2}\right)^{n+2}$, thus
$$\left\{\begin{array}{l} a_{2 k}=\frac{1}{5}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{k+1}\right]^{2} ; \\ a_{2 k+1}=\frac{1}{5}\left[(-1)^{k}+\left(\frac{1+\sqrt{5}}{2}\right)^{2 k+3}+\left(\frac{1-\sqrt{5}}{2}\right)^{2 k+3}\right] . \end{array}\right.$$

It is not difficult to verify that $\quad a_{2 k} \cdot a_{2 k+2}=a_{2 k+1}^{2}$.
Finally, we prove the conclusion of this problem by mathematical induction. Clearly, the conclusion is correct when $n=1$. Suppose $a_{2 n}$ is a perfect square, then by (3) we know $a_{2 n+2}$ is a perfect square, therefore the conclusion holds for any natural number $n$.