Reasoning about inequalities involving floor functions

86 Views Asked by At

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

There are 1 best solutions below

2
On BEST 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.