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, which combined with the above, gives

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

By definition of "floor", [[x]/a] ≤ [x]/a < [[x]/a]+1, so, combining this
fact with the above, we get

[[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

Observe that a[x/a] is an integer, and since a[x/a] ≤ x, we see that a[x/a]
is an integer that does not exceed x. Focusing on the integers that do not
exceed x, we can see that [x] is the largest such integer, and a[x/a] is also
such an integer, so a[x/a] ≤ [x]. Combining this with the first
inequality, above, we get

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

which is the contradiction that completes the proof.

### 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 this Math Help site is
Graeme McRae.