Probability that the sum of two integers in $\{1,\dots,n\}$ equals a perfect square I found the following question in MIT OCW's Mathematical Problem Solving and I'd like to know if my solution is ok:
"Let $p_n$ be the probability that $c+d$ is a perfect square when the integers $c$ and $d$ are selected independently at random from the set $\{1,\dots,n\}$. Show that $\lim_{n\to \infty} p_n\sqrt{n}$ exists, and express this limit in the form $r(\sqrt{s}-t)$ where $s$ and $t$ are integers and $r$ is a rational number."
To me, it looks like that
$$p_n= \sum_{k=2}^{\lfloor\sqrt{n}\rfloor} \sum_{i=1}^{k^2-1} P\left(c=i,d=k^2-i\right)=\sum_{k=2}^{\lfloor\sqrt{n}\rfloor}\sum_{i=1}^{k^2-1} \frac{1}{n^2}=\frac{\lfloor\sqrt{n}\rfloor(2\lfloor\sqrt{n}\rfloor^2+3\lfloor\sqrt{n}\rfloor-5)}{6n^2}$$
for $n\ge 4$ and hence $\lim p_n\sqrt{n}=\frac{1}{3}$ using $\lfloor\sqrt{n}\rfloor\le \sqrt{n}<\lfloor\sqrt{n}\rfloor+1$ and sandwich theorem.
However, the form the problem tells to write the answer makes me think I may have made some mistake. Can someone say whether my solution is correct or not and in negative case, where I missed? Thanks in advance!
EDIT: I realized that the question does not say that the perfect square must be in $\{1,\dots,n\}$. So I must add to the above a sum with $\lfloor \sqrt{n}\rfloor<k\le \lfloor\sqrt{2n}\rfloor$, being careful to the restrictions that $1\le c,d\le n$. Hence:
$$p_n=\sum_{k=2}^{\lfloor\sqrt{n}\rfloor}\sum_{i=1}^{k^2-1} \frac{1}{n^2}+\sum_{k=\lfloor\sqrt{n}\rfloor+1}^{\lfloor\sqrt{2n-1}\rfloor} \sum_{i=k^2-n}^{n-1} \frac{1}{n^2}=$$
$$=\frac{m_n(2m_n^2+3m_n-2)}{3n^2}-\frac{q_n(q_n+1)(2q_n+1)}{6n^2}+\frac{2q_n}{n}-\frac{2m_n}{n}$$
where $m_n=\lfloor \sqrt{n}\rfloor$ and $q_n=\lfloor \sqrt{2n-1}\rfloor$. We can compute
$$\lim_n \frac{m_n(2m_n^2+3m_n-2)}{3n^{3/2}}=\frac{2}{3}$$
$$\lim_n \frac{q_n(q_n+1)(2q_n+1)}{6n^{3/2}}=\frac{2\sqrt{2}}{3}$$
$$\lim_n \frac{2q_n}{\sqrt{n}}=2\sqrt{2}$$
$$\lim_n \frac{2m_n}{\sqrt{n}}=2$$
Therefore
$$\lim_{n\to \infty}\ p_n\sqrt{n}=\frac{4}{3}(\sqrt{2}-1)\approx 0.552284749831$$

Your solution is correct, and seems to agree with numerics I ran for $n=10^4$ (I got $0.55227$, and it seems harder to run this for much higher numbers).
The presentation of your solution could be a bit improved, since it isn't really clear where $m_n$ or $q_n$ come from, or what they signify. It might also help, in writing out the sum, to find the number of pairs $(a,b)$ of integers between $1$ and $n$ for which $a+b$ is a square; you just need to divide this by $n^2$ to get the probability you desire, and it keeps some of the notation similar. Otherwise, your solution is quite good.
