1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Larry Freeman Apr 8 at 6:01
  • $\begingroup$ You are welcome. You're doing a good job with your explanations. $\endgroup$ – John Omielan Apr 8 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.