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$$
 A: 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.
A: When you choose two integers uniformly at random in $\{1, 2, ..., n\}$, the probability that the sum is $i$ is
$$
P(i) = \frac{n - |n+1 - i|}{n^2} = \frac{1}{n^2}\begin{cases}i -1 & 2 \le i  \le n+1 \\ 2n+1-i & n+1 \le i \le 2n \\ 0 & \mathrm{else}\end{cases}
$$
So you get
$$P(sq) = \sum_{k = 2}^{\lfloor\sqrt{n}\rfloor}\frac{k^2-1}{n^2} + \sum_{k = \lfloor\sqrt{n}\rfloor + 1}^{\lfloor \sqrt{2n}\rfloor}\frac{2n+1 - k^2}{n^2} $$
And doing the sums gives
$$
P(sq)= \frac{\lfloor\sqrt{n}\rfloor(2\lfloor\sqrt{n}\rfloor^2 + 3\lfloor\sqrt{n}\rfloor - 6n - 5)}{3n^2}-\frac{\lfloor \sqrt{2n}\rfloor(2\lfloor \sqrt{2n}\rfloor^2 + 3\lfloor \sqrt{2n}\rfloor - 12n - 5)}{6n^2}.
$$
Letting $\epsilon = \sqrt{n} - \lfloor\sqrt{n}\rfloor$ and $\delta = \sqrt{2n}-\lfloor \sqrt{2n}\rfloor$, where $0 \le \epsilon,\delta < 1$, we have
$$
P(sq) = \frac{4(\sqrt{2}-1)}{3\sqrt{n}} + O\left(\frac{1}{n^{3/2}}\right).
$$
So the limit exists and is equal to $(4/3)(\sqrt{2}-1)$, as you found.
