First terms of this sequence is $1,2,4,6,9,11,13,15$. Now suppose that $a_k\leq (k-1)^2+1$ for $k\leq N-1$ where $N\geq 9$. Let's prove that $a_{N}\leq (N-1)^2+1$. Consider $S=\{(N-2)^2+2,...,(N-1)^2+1\}$ and $A=\{a_1,...,a_{N-1}\}$. $S$ and $A$ have no common element. Assume that $a_N$ is not in $S$. $|S|=2N-3$ and $|A|=N-1$ hence there must exists some $a_i$ such that both $(N-2)^2+l+a_i$ and $(N-2)^2+l+m+a_i$ are perfect squares for $2\leq l<l+m\leq 2N-4$. \[\sqrt{(N-2)^2+l+m+a_i}\geq \sqrt{(N-2)^2+l+a_i}+1\]\[(N-2)^2+l+m+a_i\geq (N-2)^2+l+a_i+1+2\sqrt{(N-2)^2+l+a_i}\]\[2N-4>m\geq 1+2\sqrt{(N-2)^2+l+a_i}\geq 1+2(N-1)\geq 2N-1\]Which is impossible as desired.$\blacksquare$

Let's use strong induction, base case is trivial. We wish to show $a_{n+1}\leq n^2+1$. It comes down to a single lemma: Lemma: There is at most one $(n-1)^2+1 < q \leq n^2+1$ for wich $a_i+q =t^2$, for each $i=1,2,\dots,n$. Proof: If there were $q_1>q_2$ we would have: $q_1-q_2=t_1^2-t_2^2\geq (n+1)^2-n^2 = 2n+1$. Because $q_1,q_2>(n-1)^2$, but that's a contradiction because $q_1-q_2<(n^2+1)-((n-1)^2+1) = 2n-1$. $_{\blacksquare}$ But because there are more than $n$ such $q's$ ($2n-2$ to be precise) there must be at least one $q$ for which there is no $a_i$ with $a_i+q=t^2$ and that means $a_{n+1}\leq n^2+1$, as we wanted.$_{\blacksquare}$