Let pn be the probability that two numbers selected independently and randomly from {1, 2, 3, ... , n} have a sum which is a square. Find limn→∞ pn √n.
Solution
Answer: 4(√2 - 1)/3.
There are m2 - 1 ordered pairs with sum m2 for m2 <= n, and 2n - m2 + 1 for m2 > n (and ≤ 2n). Hence the total number of ordered pairs taken from {1, 2, ... , n} which sum to a square is ∑1[√n] (m2 - 1) + ∑[√n + 1][√(2n)] (2n - m2 + 1).
Now ∑1N m2 = 1/3 N3 + O(N2). Also removing the [ ] from the limits gives an error of O(n). So we get:
1/3 n3/2 + 2(√2 - 1)n3/2 - 1/3 ( √(2n)3 - √n3) + O(n).
pn = 1/n2 x no. of pairs which sum to a square. So pn √n = (1/3 + 2(√2 - 1) - 1/3 ( 2√2 - 1) ) + O(n)/n3/2 which tends to the limit (1/3 + 2(√2 - 1) - 1/3 ( 2√2 - 1) ) = 4(√2 - 1)/3.
© John Scholes
jscholes@kalva.demon.co.uk
16 Jan 2002