If $| f(p + q) – f(q)| \le \dfrac pq$ for all $p$ and $q\in \mathbb Q$ & $q\ne 0$, show that $\sum_{i=1}^k| f(2^k ) – f(2^i ) |\le \dfrac{k(k – 1)}2$

Question

The following question is taken from the practice set of JEE exam.

If $| f(p + q) – f(q)| \le \dfrac pq$ for all $p$ and $q \in \mathbb Q$ & $q \ne 0$, show that $\sum_{i=1}^k| f(2^k ) – f(2^i ) |\le \dfrac{k(k – 1)}2$

$| f(2^k ) – f(2^1 ) |\le \dfrac{2^k-2}{2}=2^{k-1}-1$

$| f(2^k ) – f(2^2 ) |\le \dfrac{2^k-2^2}{2^2}=2^{k-2}-1$

.

.

.

$| f(2^k ) – f(2^{k-1} ) |\le \dfrac{2^k-2^{k-1}}{2^{k-1}}=2^1-1$

Adding all this, we get the required LHS$\le(2+2^2+...2^{k-1})-(k-1)=2(2^{k-1}-1)-k+1=2^k-k-1$

How to get the desired RHS?

Answer 1

Hint: For all $q\in\mathbb{Q}\setminus\{0\}$, $|f(2q) - f(q)| \le 1$, so for all $n\in\mathbb{N}$, $|f(2^n q) - f(q)| \le n$. (Why?)

Answer 2

After the hints given by @Amit_Rajaraman and @leoli1, I am attempting the solution:

$|f(2^k)-f(2^i)|\le|f(2^k)-f(2^{k-1})|+|f(2^{k-1})-f(2^{k-2})|+...+|f(2^{i+1})-f(2^i)|$

$|f(2^k)-f(2^i)|\le\dfrac{2^k-2^{k-1}}{2^{k-1}}+\dfrac{2^{k-1}-2^{k-2}}{2^{k-2}}+...+\dfrac{2^{i+1}-2^i}{2^i}$

$|f(2^k)-f(2^i)|\le(2-1)+(2-1)+...(k-i)\text{times}=k-i$

So, $\sum_{i=1}^k|f(2^k)-f(2^i)|\le k\cdot k-\dfrac{k(k+1)}2=\dfrac{k(2k-k-1)}2=\dfrac{k(k-1)}2$