If n is a positive integer, prove that [sqrt(n) + sqrt(n+1)] = [sqrt(4n+2)], where [x] denotes as usual the greatest integer not exceeding x.

This marvellous problem is from the 8th William Lowell Putnam Mathematical Competition. When I first saw it I thought there had to be a typo. I am interested if anybody has come up with any generalisations to this problem. I have been unable to extend this result in any way.

It is not easy to see how to approach such a problem. My first thought was to look at the difference between the squares and that is not such a bad way to begin. See where that takes you.

We are looking at a property of the square root function f(x) = sqrt(x), x > 0. Now f is concave down (f '' < 0) on x > 0 so (1/2)(f(n) + f(n+1)) < f(1/2(n+(n+1))) by your standard convexity condition (aka as Jensen's Inequality).Simplifying the expression gives the inequality sqrt(n) + sqrt(n+1) < sqrt(4n+2) for all x > 0. It follows that [sqrt(n) + sqrt(n+1)] <= [sqrt(4n+2)]. This is the key result that sets up the rest of the proof.

Let's assume the identity is false and establish a contradiction. Assume that there exists an integer j>0 with [f(j) + f(j+1)] != [f(4j+2)]. Let k=[f(4j+2)]. We have f(j)+f(j+1) < k <= f(4j+2). Squaring the inequalities gives 2j + 1 + 2f(j)f(j+1) < k^2 <= 4j + 2 which rearranges to 2f(j)f(j+1) < k^2 - 2j - 1 <= 2j + 1. Squaring the inequalities again yields 4j^2 + 4j < (k^2-2j-1)^2 <= (2j+1)^2 = 4j^2 + 4j + 1. This last set of inequalities is astonishing since the first and last numbers are consecutive integers. This means that the inner term which is an integer satisfies (k^2 - 2j - 1)^2 = (2j+1)^2 or simplifying, k^2 = 4j + 2. Now perfect squares k^2 = 0 (mod 4) or 1 (mod 4) as can be readily established by squaring even and odd numbers (if n=2m n^2=4m^2 and if n=2m+1 then n^2=4(m^2+m)+1). Hence we have the contradiction we require which establishes the desired result.

Using this method of solution I can't see how to generalise the result in any way. Anyone have any thoughts?