Author |
Topic: Floor function sum (Read 700 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
 |
Floor function sum
« on: Mar 15th, 2003, 10:11am » |
 Quote  Modify
|
Let x be a real number and n a positive integer. Show that
[x] + [x + 1/n] + ... + [x + (n-1)/n] = [nx],
where [x] is the greatest integer less than or equal to x.
|
|
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Floor function sum
« Reply #1 on: Mar 18th, 2003, 2:34am » |
Quote Modify
|
I don't think there's a point in hiding all this, so here goes:
Let Sn(x) = [x] + [x + 1/n] + ... + [x + (n-1)/n] = sumj=0n-1 [x + j/n]
Now split x into an integer m and a real component y:
x = m + y with 0 <= y < 1, implying [x] = m
So Sn(x) = nm + sumj=0n-1 [y + j/n]
We know that 0 <= j/n < 1 (for all j) and likewise for y. Therefore
0 <= [y + j/n] < 2,
so every member of the sum is either 0 or 1.
To determine the number of non-zero members, define j0 as the smallest index for which [y + j/n] = 1, or
y + j0/n > 1
ny + j0 > n
j0 > n(1-y)
Now, the number of ones is
(n-1) - j0 + 1 = [ n - n(1-y) ] = [ny]
Finally, we have
Sn(x) = nm + [ny] = [nm + ny] = [n(m+y)] = [nx]
qed
Maybe there's more elegant a way to prove this?
|
| « Last Edit: Mar 18th, 2003, 2:37am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: Floor function sum
« Reply #2 on: Mar 18th, 2003, 2:09pm » |
Quote Modify
|
Here's a hint, that perhaps makes the result "jump out" -- "First satisfy yourself the result is true for n = 10..."
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Floor function sum
« Reply #3 on: Mar 18th, 2003, 5:39pm » |
Quote Modify
|
The way I solved this one has similarities to wowbagger's solution:
Let x=m+q/n+e where m and q are integers (0<=q<n) and 0<=e<1/n.
The sum involves terms of the form [x+i/n] with i an integer from 0 to n-1. For n-q of these terms i<n-q so [x+i/n]=m. For q of these terms i>=n-q and [x+i/n] equals m+1. So the sum equals
m*(n-q)+(m+1)*q = m*n+q = n*(m+q/n) = [n*(m+q/n+e)] = [n*x].
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: Floor function sum
« Reply #4 on: Mar 22nd, 2003, 8:11pm » |
Quote Modify
|
Here is my solution, which is essentially the same as SWF's.
[x] + [x + 1/n] + ... + [x + (n-1)/n] = [nx].
The result is trivial for n = 1.
For n > 1, write x in base n: x = [x] + 0.d1d2d3..., where d1... are digits between 0 and n-1.
Then nx = e0 + 0.d2d3..., where e0 = n[x] + d1.
On the left hand side, if d1 = 0, all the terms equal [x]; otherwise
[x] + [0.rd2d3...] = [x], for d1 <= r <= n-1, while
[x] + 1 + [0.sd2d3...] = [x] + 1, for 0 <= s <= d1-1.
There are n terms, d1 of which equal [x] + 1, so the sum is n[x] + d1, equal to [nx], above.
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print