<s>[INST] Inequality $\sum^{k}_{i=1}\sum^{n}_{j=k}{{1}\over{j - i + 1}} \le n$ I was proving a statement and have finished all the other part, the remaining boiling down to proving the inequality below (if I proved the other part correctly):
$$\sum^{k}_{i=1}\sum^{n}_{j=k}{{1}\over{j - i + 1}} \le n$$
where $1 \le i \le k \le j \le n$.
I wrote a simple function taking $k$ and $n$ as parameters to compute the left side and the result never exceeds $n$. Also it seems that the maximum is reached when $k = n / 2$. Any ideas would be appreciated!
Thanks...
 [/INST] Proof: Define $s=\sum^{k}_{i=1}\sum^{n}_{j=k}{{1}\over{j - i + 1}}$. We prove the required inequality by factoring out common and distinct summand $\frac{1}{d+1}$, where $d=j-i$. The region of summation $\{1,2,...,k\}\times\{k,k+1,...,n\}$ is partitioned into 3 parts, with 2 isosceles right triangles sandwiching 1 parallelogram with two 45 degree angles. We distinguish 2 cases:
1) $n\le 2k-1$
The summation over the 3 partitions are:
$$\begin{align}
s_1 &= \sum_{i=0}^{n-k}\frac{d+1}{d+1}, \\
s_2 &= \sum_{d=1}^{2k-n-1} \frac{n-k+1}{n-k+1+d}, \\
s_3 &= \sum_{d=1}^{n-k} \frac{n-k+1-d}{k+d} = (n+1)\sum_{d=1}^{n-k}\frac{1}{k+d} - (n-k).
\end{align}$$
Since the summands are decreasing function of d, we bound the summations by the integration of the summands.
$$s_2 < (n-k+1)\int_0^{2k-n-1}\frac{1}{n-k+1+x}=(n-k+1)\ln\frac{k}{n-k+1},$$
and
$$s_3+n-k < (n+1)\int_0^{n-k}\frac{1}{k+x}dx=(n+1)\ln\frac{n}{k}.$$
2) $n\ge 2k-1$
$$\begin{align}
s_1 &= \sum_{i=0}^{k-1} \frac{d+1}{d+1} = k, \\
s_2 &= k\sum_{d=1}^{n-2k+1} \frac{1}{k+d} <k\int_0^{n-2k+1}\frac{1}{k+x}dx = k\ln\frac{n+1-k}{k}, \\
s_3 &= \sum_{d=1}^{k-1} \frac{d}{n-d+1} = (n+1)\sum_{d=1}^{k-1}\frac{1}{n+1-i}-(k-1) \\
&<(n+1)\int_1^k \frac{1}{n+1-x}dx = (n+1)\ln\frac{n}{n+1-k}-(k-1).
\end{align}$$

For both cases, put the parts $s_1, s_2, s_3$ together, we get the same expression
$$\begin{align}s &=s_1+s_2+s_3 \\
&= (n+1)\ln n - \big(k\ln k + (n+1-k)\ln(n+1-k)\big)+1 \\
&< (n+1)\ln n - (n+1)\ln\frac{n+1}{2} +1 \\
&\text{by the convexity of the function } x\ln x \\
&< (n+1)\Big(\ln 2-\frac{1}{n+1} \Big)+1 \\
& = (n+1)\ln 2 \\
&< 0.7(n+1).
\end{align}$$
This actually gives a slightly tighter bound for $s$. We only need to check the inequality for $n\in\{1,2\}$ to complete the proof.
Also, this proof points the way to showing $s$ achieves maximum at $k \cong \frac{n+1}{2}$ for fixed $n$.
QED
</s>