Results 1 to 10 of 10

Math Help - Is this 'floor' proof correct.

  1. #1
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722

    Is this 'floor' proof correct.

    For n \in \mathbb{N} show that \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor.

    My proof...

    If n > x both sides will be 0 so we will deal with the case when n <= x.

    Let k \neq 0 be the largest integer smaller than x such that n | k.

    Then we have \lfloor x \rfloor = k + l where l \in \mathbb{N} and 0 \leq l \leq n-1.

    So \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor =  \left\lfloor \frac{k + l}{n} \right\rfloor = \frac{k}{n} + \left\lfloor \frac{l}{n} \right\rfloor and since \frac{l}{n} < 1, \frac{k}{n} + \left\lfloor \frac{l}{n} \right\rfloor = \frac{k}{n} + 0 = \frac{k}{n}

    Now let x = \lfloor x \rfloor + \delta where 0 \leq \delta < 1.

    Then \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{k+l}{n} + \frac{\delta}{n} \right\rfloor = \frac{k}{n} + \left\lfloor \frac{l + \delta}{n} \right\rfloor.

    And since 0 \leq l \leq n-1, l + \delta < n, hence \frac{l + \delta}{n} < 1 => \left\lfloor \frac{l + \delta}{n} \right\rfloor= 0.

    So \frac{k}{n} + \left\lfloor \frac{l + \delta}{n} \right\rfloor = \frac{k}{n} + 0 = \frac{k}{n}. Hence the two are equal.


    I hope I've written this out right. To explain if it looks wrong... Imagine, 13.86/4. Then the largest integer smaller than x that n divides would be 12, l would be 1 and \delta would be 0.86.

    EDIT: I suppose this proof would also work for the case for x < n actually.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Deadstar View Post
    For n \in \mathbb{N} show that \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor.

    My proof...

    If n > x both sides will be 0 so we will deal with the case when n <= x.

    Let k \neq 0 be the largest integer smaller than x such that n | k.

    Then we have \lfloor x \rfloor = k + l where l \in \mathbb{N} and 0 \leq l \leq n-1.

    So \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor = \left\lfloor \frac{k + l}{n} \right\rfloor = \frac{k}{n} + \left\lfloor \frac{l}{n} \right\rfloor and since \frac{l}{n} < 1, \frac{k}{n} + \left\lfloor \frac{l}{n} \right\rfloor = \frac{k}{n} + 0 = \frac{k}{n}

    Now let x = \lfloor x \rfloor + \delta where 0 \leq \delta < 1.

    Then \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{k+l}{n} + \frac{\delta}{n} \right\rfloor = \frac{k}{n} + \left\lfloor \frac{l + \delta}{n} \right\rfloor.

    And since 0 \leq l \leq n-1, l + \delta < n, hence \frac{l + \delta}{n} < 1 => \left\lfloor \frac{l + \delta}{n} \right\rfloor= 0.

    So \frac{k}{n} + \left\lfloor \frac{l + \delta}{n} \right\rfloor = \frac{k}{n} + 0 = \frac{k}{n}. Hence the two are equal.


    I hope I've written this out right. To explain if it looks wrong... Imagine, 13.86/4. Then the largest integer smaller than x that n divides would be 12, l would be 1 and \delta would be 0.86.

    EDIT: I suppose this proof would also work for the case for x < n actually.

    This seems to be way too messy. I propose the following:

    1) x\geq n\Longrightarrow x=kn+0.a_1a_2\ldots\,,\,\,k\,,\,a_i\in\mathbb{N}\c  up\{0\}\,,\,\,thus\,\,\,\frac{x}{n}=k+\frac{0.a_1\  ldots}{n} \Longrightarrow \left[\frac{[x]}{n}\right]=\left[\frac{kn}{n}\right]=k=\left[\frac{x}{n}\right]

    2) x<n\Longrightarrow this case's trivial, as you pointed out.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by tonio View Post
    1) x\geq n\Longrightarrow x=kn+0.a_1a_2\ldots\,,\,\,k\,,\,a_i\in\mathbb{N}\c  up\{0\}\,,\,\,thus\,\,\,\frac{x}{n}=k+\frac{0.a_1\  ldots}{n}
    I don't think that's quite right though...
    Specifically the x = kn + 0.a_1a_2 part. Surely the 0.a_1a_2 should start with any integer less or equal to n-1

    For example. Take \frac{12.345}{5}, x=12.345, n=5. There is no k \in \mathbb{N} such that x = kn + 0.a_1a_2, the 0 in 0.a_1a_2 would be a 2 would it not?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Deadstar View Post
    I don't think that's quite right though...
    Specifically the x = kn + 0.a_1a_2 part. Surely the 0.a_1a_2 should start with any integer less or equal to n-1

    For example. Take \frac{12.345}{5}, x=12.345, n=5. There is no k \in \mathbb{N} such that x = kn + 0.a_1a_2, the 0 in 0.a_1a_2 would be a 2 would it not?

    You are, of course, right: but making that correction, mutandis-mutandis, the proof stands, since then x=kn+a_0.a_1\ldots\,,\,k,\,a_i\in\mathbb{N}\,,\,\,  0\le a_0<n , so

    \left[\frac{x}{n}\right]=\left[k+\frac{a_0.a_1\ldots}{n}\right]=k=\left[k+\frac{a_0}{n}\right]=\left[\frac{kn+a_0}{n}\right]=\left[\frac{[x]}{n}\right] , since both a_0\,,\,a_0.a_1\ldots < n

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Cheers.

    I had a feeling my answer was messy but I think it's technically correct. Your way looks a lot better though.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Aug 2009
    Posts
    19
    I'm admittedly way out of my league here, especially when constructing proofs, but why is all that rigor necessary?

    1) It seems self-evident that where n is a factor of x, also meaning x \in \mathbb{N}, then \left\lfloor\frac{x}{n}\right\rfloor = \frac{x}{n} and x=\lfloor x \rfloor.
    2) For 0\leq y<1, \left\lfloor\frac{x}{n}\right\rfloor > \left\lfloor\frac{x-y}{n}\right\rfloor \iff n is a factor of x.
    3) Since 0\leq x-\lfloor x \rfloor < 1, then \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor.
    Last edited by Andre; January 22nd 2010 at 04:16 PM. Reason: Fixed ambiguous wording in item 1
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by Andre View Post
    I'm admittedly way out of my league here, especially when constructing proofs, but why is all that rigor necessary?

    1) It seems self-evident that where n is a factor of x, also meaning x \in \mathbb{N}, then \left\lfloor\frac{x}{n}\right\rfloor = \frac{x}{n} and x=\lfloor x \rfloor.
    2) For 0\leq y<1, \left\lfloor\frac{x}{n}\right\rfloor > \left\lfloor\frac{x-y}{n}\right\rfloor \iff n is a factor of x.
    3) Since 0\leq x-\lfloor x \rfloor < 1, then \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor.
    Maybe its just me but I don't follow this at all. Can you explain it more?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Aug 2009
    Posts
    19
    Quote Originally Posted by Deadstar View Post
    Maybe its just me but I don't follow this at all. Can you explain it more?
    Sorry, I'm not at all a mathematician, so I'm not certain how to express this properly, let alone elegantly. It seems to me that it should be satisfactory to prove it for two simple and mutually-exclusive cases: x=kn and x \neq kn, as described below...

    Let n,k \in \mathbb{N}. Where x=kn, x is an integer, therefore x=\lfloor x \rfloor and \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor.

    Let y\geq 0 and y<1. This means \left\lfloor\frac{x}{n}\right\rfloor \geq \left\lfloor\frac{x-y}{n}\right\rfloor. In other words, because y\geq 0, \left\lfloor\frac{x}{n}\right\rfloor can not be less than \left\lfloor\frac{x-y}{n}\right\rfloor.

    \frac{x}{n} is an integer only when x=kn. Therefore, \left\lfloor\frac{x}{n}\right\rfloor > \left\lfloor\frac{x-y}{n}\right\rfloor \iff x=kn. Where x \neq kn, \left\lfloor\frac{x}{n}\right\rfloor = \left\lfloor\frac{x-y}{n}\right\rfloor.

    y represents x-\lfloor x \rfloor, so \lfloor x \rfloor = x-y.

    If formalized, could this be a reasonable approach to proving \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor for x=kn and x \neq kn?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by Andre View Post
    I'm not at all a mathematician
    Therefore, \left\lfloor\frac{x}{n}\right\rfloor > \left\lfloor\frac{x-y}{n}\right\rfloor \iff x=kn. Where x \neq kn, \left\lfloor\frac{x}{n}\right\rfloor = \left\lfloor\frac{x-y}{n}\right\rfloor.
    Well you have proven your first point.
    That statement is false.
    Let x=8.1,~y=0.8~\&~n=4 but \left\lfloor {\frac{x}{n}} \right\rfloor  > \left\lfloor {\frac{{x - y}}{n}} \right\rfloor \,\& \,x \ne kn
    Last edited by Plato; January 23rd 2010 at 04:22 PM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Aug 2009
    Posts
    19
    At least I proved something! Sorry for all the noise, guys.

    I see my error, thanks. I believe for my "if and only if" statement to work, y must not be greater than x-\lfloor x \rfloor, but that simply leads to a restatement of the original problem.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Correct proof?
    Posted in the Calculus Forum
    Replies: 1
    Last Post: July 12th 2011, 01:14 PM
  2. Is this proof correct?
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 11th 2010, 12:13 PM
  3. lcm, gcd proof correct?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 26th 2010, 06:32 AM
  4. proof floor function
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 13th 2009, 03:16 AM
  5. Proof of n^5 = n mod 5 .. is this correct?
    Posted in the Algebra Forum
    Replies: 4
    Last Post: November 9th 2006, 08:24 PM

Search Tags


/mathhelpforum @mathhelpforum