Mathematical Reflections 2014, Issue 4 - Problem J307

Problem:
Prove that for each positive integer $n$ there is a perfect square whose sum of digits is equal to $4^n$.

Proposed by Mihaly Bencze.

Solution:
Consider the sequence $$\begin{array}{rcl}a_1&=&4 \\ \qquad a_n&=&\underbrace{11\ldots1}_{n-1 \textrm{ times}}0\underbrace{22\ldots2}_{n-1 \textrm{ times}}4, \end{array} \qquad n \geq 2.$$
Every term of the sequence is a perfect square. Indeed, $a_0$ is clearly a perfect square and $$\begin{array}{lll} a_n&=&\dfrac{10^{n-1}-1}{9}\cdot10^{n+1}+2\cdot\dfrac{10^{n-1}-1}{9}\cdot10+4\\ &=&\dfrac{10^{2n}-8\cdot10^n+16}{9}\\&=&\left(\dfrac{10^n-4}{3}\right)^2, \end{array}$$ where $n \geq 2$.
Furthermore, if $s$ denotes the sum of the digits of $a_n$, we have $s(a_1)=4$ and $s(a_n)=(n-1)+2(n-1)+4=3n+1$ for all $n \geq 2$. Since $4^n \equiv 1 \pmod{3}$ for all $n \in \mathbb{N}$, we have that for all $n \in \mathbb{N}$ there exists $k \in \mathbb{N}$ such that $4^n=3k+1=s(a_k)$ and the conclusion follows.