Algebraic Techniques 05 - Monotonicity and Floor Function

• $f:X \rightarrow X$ is non-empty subset of $\; \mathbb{R}$ and $\; f^{[n]}(x) = x$ where $\; x \in X$ and $\; n \geq 1$. Prove the following statements.
• Find solutions of the following system of equations.
• Find solutions of the following system of equations.
• Prove Hermite’s identity. That is, show that the following equation holds for any real number $\, x$ and any positive integer $\, n$.
• For all positive integer $\, n$, prove the following equation.
• For any real number $\, x$ and any positive integer $\, n$, prove the following equation.
• For all positive integer $\, n$, prove the following equation.
• $a_n$ is a sequence of positive integers and is defined as follows. Find all positive integers of $\, a_n$.
• Reference

$f:X \rightarrow X$ is non-empty subset of $\; \mathbb{R}$ and $\; f^{[n]}(x) = x$ where $\; x \in X$ and $\; n \geq 1$. Prove the following statements.

$$\begin{aligned} &\text{(a) } f(x) = x \text{ if } f \text{ is increasing} \\ &\text{(b) } f(f(x)) = x \text{ if } f \text{ is decreasing and even } f(x) = x \text{ if } n \text{ is odd} \end{aligned}$$

---

[Solution] (a) Assume that $f(x) < x$.Since $f$ is increasing, $f(f(x)) < f(x)$. Iterating this step, $$\begin{aligned} x = f^{[n]}(x) < f^{[n - 1]}(x) < \cdots < f(x) < x \Longrightarrow \text{contradiction} \end{aligned}$$

In the same manner, assume that $f(x) > x$. Then $$\begin{aligned} x = f^{[n]}(x) > f^{[n - 1]}(x) > \cdots > f(x) > x \Longrightarrow \text{contradiction} \end{aligned}$$

Therefore, $f(x) = x$.

(b) Note that $f^{[2n]}(x) = f^{[n]}(f^{[n]}(x)) = f^{[n]}(x) = x$. Let $g = f \circ f$, then $f^{[2n]}(x) = g^{[n]}(x)$. So, $g^{[n]}(x) = x$. However, $g$ is increasing because $f$ is decreasing. Applying (a) to $g$, $g(x) = x$ and $f(f(x)) = x$. Lastly, if $n$ is odd, $f^{[n - 1]}(x) = x$ because $f(f(x)) = x$ and $n - 1$ is even. As a result, $x = f^{[n]}(x) = f(f^{[n - 1]}(x)) = f(x)$.

Find solutions of the following system of equations.

$$\begin{aligned} \begin{cases} 3a = (b + c + d)^3 \\ 3b = (c + d + a)^3 \\ 3c = (d + a + b)^3 \\ 3d = (a + b + c)^3 \end{cases} \end{aligned}$$

---

[Solution] Reforming the equations, $$\begin{aligned} \begin{cases} \sqrt[3]{3a} = b + c + d \\ \sqrt[3]{3b} = c + d + a \\ \sqrt[3]{3c} = d + a + b \\ \sqrt[3]{3d} = a + b + c \end{cases} \end{aligned}$$

It implies that $$\begin{aligned} a + \sqrt[3]{3a} = b + \sqrt[3]{3b} = c + \sqrt[3]{3c} = d + \sqrt[3]{3d} = a + b + c + d \end{aligned}$$

The key point is that the function $x \rightarrow x + \sqrt[3]{x}$ is injective and increasing because it is a sum of two increasing functions. Therefore, $a = b = c = d$. $$\begin{aligned} 3a = (3a)^3 = 27a^3 \Longrightarrow a = 0 \text{ or } a = \pm \frac{1}{3} \end{aligned}$$

Find solutions of the following system of equations.

$$\begin{aligned} \begin{cases} x^4 = 4y - 3 \\ y^4 = 4z - 3 \\ z^4 = 4x - 3 \end{cases} \end{aligned}$$

---

[Solution] Reforming the equations, $$\begin{aligned} \begin{cases} y = \frac{x^4 + 3}{4} \\ z = \frac{y^4 + 3}{4} \\ x = \frac{z^4 + 3}{4} \end{cases} \end{aligned}$$

It implies that $x > 0$, $y > 0$, and $z > 0$. Let $f(t) = (t^4 + 3) / 4$, then $f(t)$ is increasing for $t > 0$. The reformed system tells that it is cyclic. If $f$ is increasing and has cyclic system, it must be true that $f(x) = x$. Therefore, $x = y = z$ and $f(t) = t$, which means $t^4 + 3 = 4t$. By AM-GM, $$\begin{aligned} t^4 + 3 = t^4 + 1 + 1 + 1 \geq 4t \end{aligned}$$

and the equal sign is valid when $t = 1$. So, the solution is $(x, y, z) = (1, 1, 1)$.

Prove Hermite’s identity. That is, show that the following equation holds for any real number $\, x$ and any positive integer $\, n$.

$$\begin{aligned} \lfloor x \rfloor + \left\lfloor x + \frac{1}{n} \right\rfloor + \cdots + \left\lfloor x + \frac{n - 1}{n} \right\rfloor = \lfloor nx \rfloor \end{aligned}$$

---

[Solution] Let $x = \lfloor x \rfloor + \alpha$ for $\alpha \in [0, 1)$. Using the fact that $\lfloor x + n \rfloor = \lfloor x \rfloor + n$, $$\begin{aligned} &\lfloor x \rfloor + \left\lfloor x + \frac{1}{n} \right\rfloor + \cdots + \left\lfloor x + \frac{n - 1}{n} \right\rfloor \\ = \; &\lfloor x \rfloor + \left\lfloor \lfloor x \rfloor + \alpha + \frac{1}{n} \right\rfloor + \cdots + \left\lfloor \lfloor x \rfloor + \alpha + \frac{n - 1}{n} \right\rfloor \\ = \; &n\lfloor x \rfloor + \left\lfloor \alpha + \frac{1}{n} \right\rfloor + \cdots + \left\lfloor \alpha + \frac{n - 1}{n} \right\rfloor \\\\\\ &\lfloor nx \rfloor = \lfloor n \lfloor x \rfloor + n \alpha \rfloor = n \lfloor x \rfloor + \lfloor n \alpha \rfloor \end{aligned}$$

Let $k = \lfloor n \alpha \rfloor$ such that $\alpha \in [k/n, (k + 1)/n)$, then $k \leq n \alpha < k + 1$ and $k < n$ since $\alpha < 1$. Meanwhile, for $j \in \{ 1, 2, \cdots, n - 1 \}$, $$\begin{aligned} \left\lfloor \alpha + \frac{j}{n} \right\rfloor &= 0 \text{ or } 1, \\\\ \left\lfloor \alpha + \frac{j}{n} \right\rfloor = 1 \; \Longleftrightarrow \; &\alpha + \frac{j}{n} \geq 1 \; \Longleftrightarrow \; n \alpha \geq n - j \end{aligned}$$

It implies that $\left\lfloor \alpha + j/n \right\rfloor = 1$ only when $j \geq n - k$ because $n \alpha \geq n - j$ and $n \alpha \geq k$ for the integers $k$ and $n - j$. Therefore, $$\begin{aligned} \left\lfloor \alpha + \frac{1}{n} \right\rfloor + \cdots + \left\lfloor \alpha + \frac{n - 1}{n} \right\rfloor = \sum_{j = n - k}^{n - 1}1 = k = \lfloor n \alpha \rfloor \end{aligned}$$

For all positive integer $\, n$, prove the following equation.

$$\begin{aligned} \left\lfloor \frac{n + 2^0}{2^1} \right\rfloor + \cdots + \left\lfloor \frac{n + 2^{n - 1}}{2^n} \right\rfloor = n \end{aligned}$$

---

[Solution] Reforming the equation, $$\begin{aligned} \left\lfloor \frac{n}{2} + \frac{1}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{2^n} + \frac{1}{2} \right\rfloor = n \end{aligned}$$

By Hermite’s identity, $$\begin{aligned} \left\lfloor x + \frac{1}{2} \right\rfloor = \left\lfloor 2x \right\rfloor - \left\lfloor x \right\rfloor \end{aligned}$$

So, reformed equation can be rewritten as $$\begin{aligned} \left\lfloor \frac{n}{2} + \frac{1}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{2^n} + \frac{1}{2} \right\rfloor = n - \left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{n}{2} \right\rfloor - \left\lfloor \frac{n}{4} \right\rfloor + \cdots + \left\lfloor \frac{n}{2^{n - 1}} \right\rfloor - \left\lfloor \frac{n}{2^n} \right\rfloor = n - \left\lfloor \frac{n}{2^n} \right\rfloor \end{aligned}$$

$\left\lfloor n / 2^n \right\rfloor = 0$ since $2^n > n$ for all $n$, then the proof is complete.

For any real number $\, x$ and any positive integer $\, n$, prove the following equation.

$$\begin{aligned} \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor \end{aligned}$$

---

[Solution] Let $k = \lfloor x / n \rfloor$, then $x/n \in [k, k + 1)$, which means that $x \in [nk, n(k + 1))$. Since floor function is non-decreasing and $n(k + 1)$ is an integer, $\lfloor x \rfloor \in [nk, n(k + 1))$. So, $\lfloor x \rfloor / n \in [k, k + 1)$ and $\left\lfloor \lfloor x \rfloor / n \right\rfloor = k$.

For all positive integer $\, n$, prove the following equation.

$$\begin{aligned} \left\lfloor \sqrt{n} + \sqrt{n + 1} \right\rfloor = \left\lfloor \sqrt{4n + 1} \right\rfloor \end{aligned}$$

---

[Solution] Let $\left\lfloor \sqrt{4n + 1} \right\rfloor = k$, then $k^2 \leq 4n + 1 < (k + 1)^2$. It is sufficient to prove that $$\begin{aligned} k^2 \leq \left( \sqrt{n} + \sqrt{n + 1} \right)^2 = 2n + 1 + 2 \sqrt{n^2 + n} < (k + 1)^2 \end{aligned}$$

The left side of this inequality is obvious because $$\begin{aligned} 2n + 1 + 2 \sqrt{n^2 + n} > 2n + 1 + 2n = 4n + 1 \geq k^2 \end{aligned}$$

In a similar manner, the right side is also true. $$\begin{aligned} 2n + 1 + 2 \sqrt{n^2 + n} < 2n + 1 + 2 \left( n + \frac{1}{2} \right) = 4n + 2 \leq (k + 1)^2 \end{aligned}$$

$a_n$ is a sequence of positive integers and is defined as follows. Find all positive integers of $\, a_n$.

$$\begin{aligned} a_n = \left\lfloor n + \sqrt{n} + \frac{1}{2} \right\rfloor \end{aligned}$$

---

[Solution] By observation, this sequence is increasing and skipping perfect squares as $2$, $3$, $5$, $6$, $7$, $8$, $10$, $\cdots$. The idea is to create new inequality to prove from these observations. Let $a_n = k$, then this sequence skips $k + 1$ only when $a_{n + 1} \geq k + 2$. That is, $$\begin{aligned} n + 1 + \sqrt{n + 1} + \frac{1}{2} \geq \left\lfloor n + 1 + \sqrt{n + 1} + \frac{1}{2} \right\rfloor \geq k + 2 \end{aligned}$$

Let $m = k - n$, then this inequality can be rewritten as $$\begin{aligned} &\sqrt{n + 1} \geq k - n + \frac{1}{2} \\\\ \Longrightarrow \; &n + 1 \geq \left( m + \frac{1}{2} \right)^2 = m^2 + m + \frac{1}{4} \\\\ \Longrightarrow \; &n \geq m^2 + m \end{aligned}$$

since $m$ and $n$ are integers. In addition, from $a_n = k$, $$\begin{aligned} &k \leq n + \sqrt{n} + \frac{1}{2} < k + 1 \\\\ \Longrightarrow \; &\left( m - \frac{1}{2} \right)^2 \leq n < \left( m + \frac{1}{2} \right)^2 \\\\ \Longrightarrow \; &m^2 - m < n \leq m^2 + m \end{aligned}$$

since $m$ and $n$ are integers. Combining the previous condition, $n = m^2 + m$. So, $k = n + m = m^2 + 2m$, which means $k + 1 = (m + 1)^2$ after adding $1$ to both sides. Therefore, this sequence skips the positive integer $k + 1$ only when $k + 1 = (m + 1)^2$ for all non-negative $m$. In other words, the sequence $a_n$ skips $a_n + 1$ only when $a_n + 1 = (a_n - n + 1)^2$. Accordingly, $a_n$ is a subset of all positive integers except for perfect squares.

Reference

[1] Titu Andreescu, 105 Algebra Problems.