# Reasoning about inequalities involving floor functions

I am working on the beginning of an inductive argument and I wanted to confirm that my base case is sound.

Let $$f(x) = \lfloor x\rfloor - \left\lfloor\dfrac{x}{2}\right\rfloor$$ where is $$x$$ is a positive real.

Let $$u,v$$ be positive integers such that $$u \ge 7$$ and $$v \ge 2$$

I am trying to show that the following base case is true:

$$f(u^2+u) - f(u^2) - f\left(\frac{u^2+u}{v}\right) + f\left(\frac{u^2}{v}\right) > 0$$

Here is my argument for the base case:

(1) Let $$a_1, a_2, a_3$$ be nonnegative integers such that $$a_1 < v$$, $$a_2 < v$$, $$a_3 < 2$$ and:

$$\left\lfloor\dfrac{u^2+u}{v}\right\rfloor = \dfrac{u^2+u-a_1}{v},\left\lfloor\dfrac{u^2}{v}\right\rfloor = \dfrac{u^2-a_2}{v},\left\lfloor\dfrac{u^2}{2}\right\rfloor = \dfrac{u^2-a_3}{2},$$

(2) Let $$b_1,b_2$$ be nonnegative numbers with each $$b_i < 2v$$ and $$b_i=a_i$$ or $$b_i = a_i+v$$ such that:

$$\left\lfloor\dfrac{u^2+u}{2v}\right\rfloor = \dfrac{u^2+u-b_1}{2v},\left\lfloor\dfrac{u^2}{2v}\right\rfloor = \dfrac{u^2-b_2}{2v}$$

(3) Since $$u^2+u$$ is even, combining all terms, I get:

$$f(u^2+u) - f(u^2) - f\left(\frac{u^2+u}{v}\right) + f\left(\frac{u^2}{v}\right) =$$

$$u - \dfrac{u^2+u}{2} + \dfrac{u^2-a_3}{2}-\dfrac{u^2+u-a_1}{v} + \dfrac{u^2+u-b_1}{2v} + \dfrac{u^2-a_2}{v} - \dfrac{u^2-b_2}{2v}$$

$$= \dfrac{u-a_3}{2} - \dfrac{u^2+u - 2a_1 + b_1}{2v} + \dfrac{u^2-2a_2 + b_2}{2v}$$

$$= \dfrac{u-a_3}{2} - \dfrac{u-2a_1+b_1+2a_2-b_2}{2v}$$

$$=\dfrac{(v-1)u -va_3 + 2a_1 - b_1 -2a_2 + b_2}{2v}$$

(4) $$\dfrac{va_3 - 2a_1 + b_1 + 2a_2 - b_2}{2v} < \dfrac{3}{2}$$ since:

• $$\dfrac{va_3}{2v} \le \dfrac{v}{2v} = \dfrac{1}{2}$$

• $$\dfrac{b_1 - 2a_1}{2v} \le \dfrac{(v + a_1) - 2a_1}{2v} \le \dfrac{v}{2v} = \dfrac{1}{2}$$

• $$\dfrac{2a_2 - b_2}{2v} \le \dfrac{2a_2 - (a_2)}{2v} = \dfrac{a_2}{2v} < \dfrac{v}{2v} = \dfrac{1}{2}$$

(5) So that:

$$f(u^2+u) - f(u^2) - f\left(\frac{u^2+u}{v}\right) + f\left(\frac{u^2}{v}\right) =$$

$$=\dfrac{(v-1)u -va_3 + 2a_1 - b_1 -2a_2 + b_2}{2v} > \dfrac{(v-1)u}{2v} - \dfrac{3}{2}$$

(6) Since $$u > 6$$ and $$v \ge 2$$:

$$\left(\dfrac{v-1}{v}\right)\dfrac{u}{2} \ge \left(\dfrac{1}{2}\right)\dfrac{u}{2} > \dfrac{6}{4}$$

which means that:

$$f(u^2+u) - f(u^2) - f\left(\frac{u^2+u}{v}\right) + f\left(\frac{u^2}{v}\right) > \dfrac{3}{2} - \dfrac{3}{2} = 0$$

Is my reasoning correct? Did I make a mistake? Is any step in my argument unclear?

## 1 Answer

I have gone through all of your steps fairly carefully and didn't see any mistakes. As for being clear, it took me a bit of time to figure out some of your lines in $$(3)$$ as you sometimes did several steps in one line. However, this is a minor point. Also, I've seen quite a few math proofs which are considerably harder to follow & figure out than what you provided.

If you're interested, the following is somewhat similar to what you did, but it takes a somewhat higher level view. First, you have

$$f(x) = \lfloor x\rfloor - \left\lfloor\dfrac{x}{2}\right\rfloor \tag{1}\label{eq1}$$

where is $$x$$ is a positive real. You are trying to show that

$$f(u^2+u) - f(u^2) - f\left(\frac{u^2+u}{v}\right) + f\left(\frac{u^2}{v}\right) > 0 \tag{2}\label{eq2}$$

is true for all positive integers $$u,v$$ with $$u \ge 7$$ and $$v \ge 2$$. Consider a positive integer $$a$$. If $$a$$ is even, i.e., $$a = 2b$$ for an integer $$b$$, then $$f(a) = \lfloor 2b\rfloor - \left\lfloor\dfrac{2b}{2}\right\rfloor = 2b - b = b = \dfrac{a}{2}$$. If $$a$$ is odd, i.e., $$a = 2b + 1$$ instead, then $$f(a) = \lfloor 2b + 1\rfloor - \left\lfloor\dfrac{2b + 1}{2}\right\rfloor = 2b + 1 - b = b + 1 = \dfrac{a + 1}{2}$$. Using this with the first $$2$$ terms of \eqref{eq2}, with $$u^2 + u$$ always being even as you've already noted, then for $$u$$ being even

$$f(u^2+u) - f(u^2) = \frac{u^2 + u}{2} - \frac{u^2}{2} = \frac{u}{2} \tag{3}\label{eq3}$$

while if $$u$$ is odd, then

$$f(u^2+u) - f(u^2) = \frac{u^2 + u}{2} - \frac{u^2 + 1}{2} = \frac{u - 1}{2} \tag{4}\label{eq4}$$

The third & fourth terms of \eqref{eq2} involve $$f\left(\dfrac{c}{v}\right)$$ for some integer $$c$$. Consider $$c = k(2v) + r$$ for some integer $$k$$, plus $$0 \le r \le 2v - 1$$. First, if $$0 \le r \lt v$$, then

$$f\left(\frac{c}{v}\right) = \left\lfloor \frac{k(2v) + r}{v}\right\rfloor - \left\lfloor\frac{k(2v) + r}{2v}\right\rfloor = 2k - k = k \tag{5}\label{eq5}$$

Next, if $$v \le r \lt 2v$$, then

$$f\left(\frac{c}{v}\right) = \left\lfloor \frac{k(2v) + r}{v}\right\rfloor - \left\lfloor\frac{k(2v) + r}{2v}\right\rfloor = 2k + 1 - k = k + 1 \tag{6}\label{eq6}$$

Next, consider a lower limit of

$$\dfrac{c}{2v} - \dfrac{1}{2} = k + \dfrac{r}{2v} - \dfrac{1}{2} \tag{7}\label{eq7}$$

If $$0 \le r \lt v$$, then \eqref{eq7} is $$\lt k$$ and, thus, the value of \eqref{eq5}. If $$v \le r \lt 2v$$, then \eqref{eq7} is $$\lt k + 1$$ and, thus, the value of \eqref{eq6}. Thus, in either case,

$$f\left(\dfrac{c}{v}\right) \gt \dfrac{c}{2v} - \dfrac{1}{2} \tag{8}\label{eq8}$$

For an upper limit, let

$$\dfrac{c}{2v} + \dfrac{1}{2} = k + \dfrac{r}{2v} + \dfrac{1}{2} \tag{9}\label{eq9}$$

If $$0 \le r \lt v$$, then \eqref{eq9} is $$\gt k$$ and, thus, \eqref{eq5}. For $$v \le r \lt 2v$$, then \eqref{eq8} is $$\ge k + 1$$ and, thus, \eqref{eq6}. Thus, in either case,

$$\dfrac{c}{2v} + \dfrac{1}{2} \ge f\left(\dfrac{c}{v}\right) \tag{10}\label{eq10}$$

The minimum value of the third & fourth terms of \eqref{eq2} would be with the minimum value of the fourth term less the maximum value of the third term. Thus, using the limits given by \eqref{eq8} and \eqref{eq10}, then

$$f\left(\frac{u^2}{v}\right) - f\left(\frac{u^2+u}{v}\right) \gt \left(\frac{u^2}{2v} - \frac{1}{2}\right) - \left(\frac{u^2 + u}{2v} + \frac{1}{2}\right) = -\frac{u}{2v} - 1 \tag{11}\label{eq11}$$

Note for $$v \ge 2$$ that $$\dfrac{v-1}{v} \ge \dfrac{1}{2}$$. Thus, if $$u$$ is even, then from \eqref{eq3},

$$\frac{u}{2} - \frac{u}{2v} - 1 = \frac{u(v-1)}{2v} - 1 \ge \frac{8}{2(2)} - 1 = 1 \tag{12}\label{eq12}$$

If $$u$$ is odd, then from \eqref{eq4},

$$\frac{u - 1}{2} - \frac{u}{2v} - 1 = \frac{u(v-1)}{2v} - \frac{3}{2} \ge \frac{7}{2(2)} - \frac{3}{2} = \frac{1}{4} \tag{13}\label{eq13}$$

Since \eqref{eq12} and \eqref{eq13} are the minimum values of the LHS of \eqref{eq2}, this shows it is $$\gt 0$$ in either case, as requested to be proven.

Note this approach doesn't make the calculations very much, if any, simpler in your particular case. I believe the main advantage of the approach is that if instead of having $$2$$ terms each of an integer & fraction, you had many more terms (e.g., $$4$$, $$6$$, $$8$$ or even more), then this method would make dealing with all of the values generally shorter & easier.

• Thanks very much for your comments. I appreciate the details. I struggle with making the argument as clear and simple as possible and am very open to your points. – Larry Freeman Apr 8 at 6:01
• You are welcome. You're doing a good job with your explanations. – John Omielan Apr 8 at 6:04