Write out the multiplication by column method, the statement is self-evident. Edit: With this intuition, the "if" part holds trivially. The "only if" part is not that obvious (as pointed out by below, strange things happen when the base is smaller), but analyzing the carries works fine.

NTstrucker wrote: Write out the multiplication by column method, the statement is self-evident. Really? Consider the following:

Click to reveal hidden text

We can fix it by proving that a(0)<=3 and k^2 has 2n-1 digits, that should work.

USJL wrote: NTstrucker wrote: Write out the multiplication by column method, the statement is self-evident. Really? Consider the following:

Click to reveal hidden text

Isn't the problem in base 10 though or does the problem asks for any general bases?

RevolveWithMe101 wrote: USJL wrote: NTstrucker wrote: Write out the multiplication by column method, the statement is self-evident. Really? Consider the following:

Click to reveal hidden text

Isn't the problem in base 10 though or does the problem asks for any general bases? The problem only asks for base 10, but my point is any solution that does not use this fact should fail as there is a counter-example in base 2. In particular, I'd see any solution that only says "simply do multiplication and there cannot be any carry" as incomplete.

First I prove if $a_0^2+a_1^2+\cdots+a_{n-1}^2<10$ then $k^2$ is palindromic. Let $P(x)=a_{n-1}x^{n-1}+\cdots+a_0$. This implies $P(x)^2 = s_{2n-2} x^{2n-2} + \cdots + s_0$ where $s_{2n-2-j}=s_j$ and for $j\le n-1$, $s_j=\sum\limits_{t=0}^j a_ja_{t-j}$. It suffices to show $s_j\le s_{n-1}\le 9$. Note $s_j=\sum\limits_{t=0}^j a_ja_{t-j}\le \frac 12 \sum\limits_{t=0}^j (a_j^2+a_{t-j}^2) \le \sum\limits_{t=0}^{n-1} a_t^2=s_{n-1}$. Now I prove $a_0^2+a_1^2+\cdots+a_{n-1}^2\ge 10$ then $k^2$ is not palindromic. Case 1: $k^2$ has $2n-1$ digits. Define $s_j$ as above. Also, let $k^2=\overline{t_{2n-2}t_{2n-3}\cdots t_0}$ Let $j$ be the smallest integer $\le n-1$ such that $s_j\ge 10$. Note $j$ exists since $s_j\ge 10$ and $j>0$ because otherwise, $s_0=a_0^2\ge 10$ which means $k^2$ has $2n$ digits. Furthermore, $s_m=t_m$ for all $0\le m\le j-1$ Since $k^2$ is a palindrome, it follows that $t_{j-1}=t_{2n-1-j}, t_{j-2}=t_{2n-j}, \cdots, t_0=t_{2n-2}$ as they are all less than 10. This means there must have been no carries from lower bits to one of bits $2n-1-j, \cdots, 2n-2$. However, this impossible because $t_{2n-j} = t_j \ge 10$. Therefore, $k^2$ is NOT a palindrome. Case 2: $k^2$ has $2n$ digits. Mod 10 works: If $k^2\equiv 1(\bmod\; 10)$ then $a_0=a_k=9$ so the leading digit of $k^2$ is 8 or 9, not 1. If $k^2\equiv 4(\bmod\; 10)$ then $a_0=a_k=8$ so the leading digit of $k^2$ is 6 or 7 or 8, not 4. If $k^2\equiv 9(\bmod\; 10)$ then $a_0=a_k\in \{3,7\}$ so the leading digit of $k^2$ is at most 6. If $k^2\equiv 6(\bmod\; 10)$ then $a_0=a_k\le 6$ so the leading digit of $k^2$ is at most 4. If $k^2\equiv 5(\bmod\; 10)$ then $a_0=a_k=5$ so the leading digit of $k^2$ is at most 3. The end.