1
$\begingroup$

I am given that the function g(x) = |x - k|, where k is the nearest integer to x. From this, I am supposed to prove that this function $\frac{g(x)-g(x+t)}{t}$ $\leq$ 1 for all x and all t $\gt$ 0 (all t below zero are implied by this too). There's several cases I've already covered:

t>1/2, 0$\leq$g(x)$\leq$1/2 so therefore g(x)-g(y) can be 1/2 at most. This means that the lhs is always less than $\frac{1}{2x}$, makng it trivial for all such t.

t<1/2, g(x) has the same k as g(x+t). By simple application of the triangle inequality:

$$\frac{|x+t-k|-|x-k|}{t} \leq \frac{|x-k|+|t|-|x-k|}{t} = \frac{|t|}{t} = 1$$

For the other case though, where the k of g(x+t) is k+1 for g(x), then I struggle. It makes intuitive sense that it is, but doing the same triangle inequality process gives me $1 + \frac{1}{t}$, which is less useful. Does anyone have any clue?

Thank you!

EDIT: Just so you can see a geometric understanding (and the reason why I feel so stupid about it) is that essentially I'm trying to prove that a line from one to the other section has gradient less than or equal to 1, which is obvious from the picture but I'm not sure how to prove it function  plotted

$\endgroup$
2
$\begingroup$

The idea is that $g$ is linear with slope $+1$ or $-1$ on each closed interval $[\frac{j}{2}, \frac{j+1}{2}]$, $j \in \Bbb Z$.

For $x < y$ let $$ a_1 < a_2 < \ldots < a_{n-1} $$ be the (possibly empty) sequence of all "half integers" between $x$ and $y$. Setting $a_0 = x$, $a_n = y$ we have that $g$ is linear with slope $\pm 1$ on each interval $[a_{j-1}, a_j]$, and $$ |g(y) -g(x) |= \left| \sum_{j=1}^n g(a_j) - g(a_{j-1}) \right | \le \sum_{j=1}^n |g(a_j) - g(a_{j-1})| \\ = \sum_{j=1}^n |a_j - a_{j-1} | = \sum_{j=1}^n (a_j - a_{j-1}) = y - x $$

More generally, if $I_1, \ldots, I_n$ are "adjacent" intervals and a function $g$ is Lipschitz-continuous (with the same Lipschitz constant $L$) on each interval $I_j$, then $g$ is Lipschitz-continuous on the union of the intervals.


Alternative approach: Let $x < y$ and $k = \lfloor x + \frac 12 \rfloor$, $l = \lfloor y + \frac 12 \rfloor$ be the nearest integers to $x$ and $y$, respectively.

Case 1: $l = k$. Then $$ |g(y) - g(x)| = ||y-k| - |x-k|| \le |(y-k) - (x-k)| = y - x \, . $$

Case 2: $l = k+1$. Then $$ |g(y) - g(x)| = \bigl||y-(k+1)| - |x-k| \bigr| \\ \le \bigl| |y-(k+1)| - \frac 12 \bigr| + \bigl| \frac 12 - |x-k|\bigr | \\ \le \bigl| y-(k+1) - \frac 12 \bigr| + \bigl| \frac 12 - (x-k)\bigr | \\ = \bigl( y - (k + \frac 12) \bigr) + \bigl( (k + \frac 12) - x \bigr) \\ = y - x \, . $$

Case 3: $l \ge k + 2$. Then $y - x \ge 1$ and $ |g(y) - g(x) | \le \frac 12 $.

$\endgroup$
  • $\begingroup$ This is a nice answer but not going to lie, from the material it's from (T.W. Korner's "The Pleasures of Counting", a book who is designed for first year/pre-uni but the author claims a confident 14 year old would understand) I assumed the solution was going to be much simpler. I had never heard of Lipschitz continuity, for example. $\endgroup$ – It'sNotALie. Dec 31 '17 at 17:15
  • $\begingroup$ @It'sNotALie.: Well, the part of Lipschitz-continuity was only an additional remark to put the problem into a more general context, the proof itself uses only the triangle inequality. – I have added another approach which might be closer to what you were thinking of, in particular the case where you "struggled" is treated in an elementary way. $\endgroup$ – Martin R Jan 1 '18 at 12:02
  • $\begingroup$ that was a lot more transparent to me, thank you very much! $\endgroup$ – It'sNotALie. Jan 1 '18 at 16:47

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.