I’ll demonstrate one way to approach the problem, leaving some of the intermediate proofs and the final step of the argument to you.
We have $a_1=u+v$ and
$$\begin{align*}
a_{2m}&=a_{m}+u\\
a_{2m+1}&=a_{m}+v\;.
\end{align*}$$
Gathering a little data, we find that
$$\begin{array}{l|l}
a_1=u+v&s_1=u+v=a_1\\ \hline
a_2=2u+v\\
a_3=u+2v&s_3=4u+4v=4a_1\\ \hline
a_4=3u+v\\
a_5=2u+2v\\
a_6=2u+2v\\
a_7=u+3v&s_7=12u+12v=12a_1\\ \hline
a_8=4u+v\\
a_9=3u+2v\\
a_{10}=3u+2v\\
a_{11}=2u+3v\\
a_{12}=3u+2v\\
a_{13}=2u+3v\\
a_{14}=2u+3v\\
a_{15}=u+4v&s_{15}=32u+32v=32a_1\\ \hline
\end{array}$$
We notice that at least as far as our data go, if $2^{n-1}\le k<2^n$, then the coefficients of $u$ and $v$ in $a_k$ sum to $n+1$. It appears, moreover, that if $k=2^{n-1}+\ell$, then the coefficients of $u$ and $v$ in $a_k$ and $a_{2^n-1-\ell}$ are interchanged, so that $a_k+a_{2^n-1-\ell}=(n+1)(u+v)=(n+1)a_1$, and therefore
$$\sum_{k=2^{n-1}}^{2^n-1}a_k=2^{n-2}(n+1)a_1\tag{1}$$
for $n\ge 2$, and
$$s_{2^n-1}=\sum_{k=1}^{2^n-1}a_k=\left(1+\sum_{k=0}^{n-2}2^k(k+3)\right)a_1\;.\tag{2}$$
It’s not too hard to prove $(1)$ by induction on $n$, and that proves $(2)$. It’s possible to solve $(2)$ in closed form starting from scratch, but there’s a shortcut: for $n=1,2,3,4$ the coefficients of $a_1$ in $s_{2^n-1}$ are $1,4,12,32$; if we feed that to The On-Line Encyclopedia of Integer Sequences, the first return is A$001787$, and a quick computation shows that this sequence matches the coefficients of $a_1$ in $s_{31}$ and $s_{63}$ as well. If it really is our sequence, then
$$s_{2^n-1}=n2^{n-1}a_1\tag{3}$$
for $n\ge 1$. Given $(2)$, it’s easy to prove $(3)$ by induction on $n$.
Now it suffices to prove that if $a_1$ is any positive integer, there are infinitely many positive integers $n$ such that $n2^{n-1}a_1$ is a perfect square, and this is pretty straightforward.
u,vknown to be different? – John Dvorak Oct 13 '13 at 04:30