Greatest integer <= X problem

[jay_shark]

Show that [sqrt)4n+1)]=[sqrt(4n+2)] = [sqrt(4n+3)]
=[sqrt(n) + sqrt(n+1)] for all positive integers n .

Remember that [x] is the greatest integer less than or equal to x .

I'm interested in alternate solutions to this problem . Feel free to make any comments you wish .

[gumpzilla]

The only time [sqrt(n)] != [sqrt(n+1)] is when n+1 is a perfect square. So, if we show that 4n+2 and 4n+3 can never be perfect squares, then the first half of the problem is proven.

4n+2 = 2*(2n+1), where 2n+1 is odd. So 4n+2 can never be a perfect square, since it has an unpaired factor of 2.

4n+3 doesn't work either. We can get the nth square number by adding the first n odd natural numbers. Modulo 4, those are congruent to 1, 3, 1, 3, 1, 3 . . ., so that congruent to modulo 4 the squares are 1, 0, 1, 0, 1, 0, . . . and you'll never get a square of the form 4n+3. (This argument actually holds for 4n+2 as well, obviously, but the parity argument above is a little more straightforward.)

Proving the last bit seems like it must be the hard part. I'll think on that for a bit.

EDIT: How's this.

( sqrt(n) + sqrt(n+1) )^2 = 2n+1 + 2*sqrt(n^2 + n)

n^2 &lt; n^2 + n &lt; n^2 + 2n + 1, so
2n &lt; 2*sqrt(n^2 + n) &lt; 2n + 2, so
4n+1 &lt; ( sqrt(n) + sqrt(n+1) )^2 &lt; 4n+3,

and since floor(sqrt(4n+3)) = floor(sqrt(4n+1)), floor(sqrt(n) + sqrt(n+1)) is the same, too.

I found this MUCH easier than most of the problems you've been posting. This took me about 4 minutes.

[djames]

Gump, nice!

[jay_shark]

Nice solution Gump !

[armPitt]

induction works here too...right?

[gumpzilla]

[ QUOTE ]
induction works here too...right?

[/ QUOTE ]

What's your inductive proof?