The "floor" function, denoted [x], refers to the largest integer that does not exceed x.

Definition of "floor": [x] ≤ x, and if k is an integer, k ≤ x, then k ≤ [x]

Definition of the "floor function":  [x] is defined as the largest integer that does not exceed x.  Therefore, [x] ≤ x, and if any other integer, k, does not exceed x, then k ≤ [x], because [x] is the largest integer that does not exceed x.

Lemma 1: if y ≤ x then [y] ≤ [x]

Lemma 1: if y ≤ x then [y] ≤ [x]

Proof:  [y] ≤ y ≤ x, so [y] ≤ x.  Also, [x] ≤ x. Since [y] and [x] are both integers that do not exceed x, [y] ≤ [x], by the definition of [x].

Corollary:  if [y] > [x] then y > x, which is the contrapositive of lemma 1.

Lemma 2: [x]+1 > x

Lemma 2: [x]+1 > x

Proof: Suppose to the contrary that [x]+1 ≤ x.  By definition of "floor", if any integer does not exceed x, then that integer does not exceed [x], so [x]+1 ≤ [x].  Subtracting [x] from both sides, we get 1 ≤ 0, a contradiction, so the lemma is proved.

Theorem 1: [x/a] = [[x]/a]

Theorem 1:  if x is a real number, and a is a natural number, then [[x]/a] = [x/a]

Proof:  If they're different, then [[x]/a] < [x/a], by lemma 1.  Assume for contradiction that's the case.  Since [[x]/a] and [x/a] are unequal integers, they must differ by at least 1, so by lemma 2,

[[x]/a]+1 ≤ [x/a]

By definition of "floor", [[x]/a] ≤ [x]/a < [[x]/a]+1, and [x/a] ≤ x/a, so

[[x]/a] ≤ [x]/a < [[x]/a]+1 ≤ [x/a] ≤ x/a

Extracting three of these expressions from the inequality, above,

[x]/a < [x/a] ≤ x/a

Now, multiply through by a, giving you 

[x] < a[x/a] ≤ x

Thus we see that a[x/a] is an integer that does not exceed x, so a[x/a] can't be larger than [x], a contradiction proving the result.

Internet references

Related pages in this website

Counting Primes method of proving the following are integers: C(n,k) = n!/(k!(n-k)!), (2a)!(2b)!/((a+b)!a!b!)

Combination identities proves the standard combination identities, including C(n,k) = C(n-1,k-1) + C(n-1,k) and many others.

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]