, 2022

($\Rightarrow$) Step 1. We use exhaustive case analysis to discuss the leading digit and the last digit of $k^2$. First, since $10^{n-1} \le k < 10^n$, we know $10^{2n-2} \le k^2 < 10^{2n}$, hence $k^2$ has either $2n-1$ digits or $2n$ digits.

If $k^2$ has $2n$ digits, then by exhaustive enumeration we obtain the following table:

Here the possible leading digit(s) of $k^2$ are the positive integers lying between $\lfloor \frac{a_{n-1}^2}{10} \rfloor$ and $\lfloor \frac{(a_{n-1}+1)^2}{10} \rfloor$. From the table above, we see that if $k^2$ has $2n$ digits, then $k^2$ cannot be a palindrome. Hence if $k^2$ is a palindrome, then $k^2$ must have $2n-1$ digits.

Step 2. For $0 \le m < n$ define $c_m = \sum_{i=0}^{m} a_i a_{m-i}$. Then, from the condition that $k$ is a palindrome we know
$$k^2 = c_{n-1} \cdot 10^{n-1} + \sum_{i=0}^{n-2} (10^i + 10^{2n-2-i}).$$
And since $k^2$ is also a palindrome, we may assume there exist integers $b_0, b_1, \dots, b_{n-1}$ between 0 and 9 such that
$$k^2 = b_{n-1} \cdot 10^{n-1} + \sum_{i=0}^{n-2} b_i (10^i + 10^{2n-2-i}).$$
We prove the following lemma.

Lemma. Let $n$ be a positive integer, let $c_0, c_1, \dots, c_{n-1}$ be nonnegative integers, and let $b_0, b_1, \dots, b_{n-1}$ be integers between 0 and 9. If
$$c_{n-1} \cdot 10^{n-1} + \sum_{i=0}^{n-2} (10^i + 10^{2n-2-i}) = b_{n-1} \cdot 10^{n-1} + \sum_{i=0}^{n-2} b_i (10^i + 10^{2n-2-i}), \quad (1)$$
then $b_i = c_i$ for all $0 \le i < n$.

Proof of Lemma. We induct on $n$. When $n=1$ the claim is obvious. Now assume the claim holds for $n-1$. Taking both sides of (1) modulo $10$ gives
$$c_0 \equiv b_0 \pmod{10}.$$
So we may write $c_0 = b_0 + 10t$. Since $0 \le b_0 \le 9$ and $c_0 \ge 0$, we get $t \ge 0$, hence $c_0 \ge b_0$.

On the other hand, observing (1) again, we have
$$c_0(1 + 10^{2n-2}) \le \text{LHS} = \text{RHS} < (b_0 + 1)(1 + 10^{2n-2}),$$
so $c_0 \le b_0$. Therefore $c_0 = b_0$.

Cancelling the term $c_0(1 + 10^{2n-2})$ from both sides of (1) and dividing both sides by $10$, we get
$$c_{n-1} \cdot 10^{n-2} + \sum_{i=1}^{n-2} (10^{i-1} + 10^{2n-3-i}) = b_{n-1} \cdot 10^{n-2} + \sum_{i=1}^{n-2} b_i (10^{i-1} + 10^{2n-3-i}). \quad (2)$$
We find that (2) allows us to apply the induction hypothesis to obtain $b_i = c_i$ for $1 \le i < n$, which completes the proof by mathematical induction.

Returning to the original proof. By the lemma we know
$$\sum_{i=0}^{n-1} a_i a_{n-1-i} = c_{n-1} = b_{n-1} < 10,$$
and since $k$ is a palindrome we know $a_{n-1-i} = a_i$, hence we obtain $\sum_{i=0}^{n-1} a_i^2 < 10$.

($\Leftarrow$) Again let $c_m = \sum_{i=0}^{m} a_i a_{m-i}$. From the condition that $k$ is a palindrome we have
$$k^2 = c_{n-1} \cdot 10^{n-1} + \sum_{i=0}^{n-2} c_i (10^i + 10^{2n-2-i}).$$
Here it suffices to prove that $c_m < 10$ for $m < n$. In this way, $k^2 = \overline{c_0c_1\cdots c_{n-2}c_{n-1}c_{n-2}\cdots c_1c_0}$ is a palindrome. For $m < n$, we have
$$\begin{aligned} c_m &= \sum_{i=0}^{m} a_i a_{m-i} \\ &\le \sum_{i=0}^{m} \frac{a_i^2 + a_{m-i}^2}{2} \quad (\text{by AM-GM}) \\ &= \sum_{i=0}^{m} a_i^2 < 10. \end{aligned}$$