Given constrain $m=a_1>a_2>...>a_n$ and the elements are integer prove $\sum \frac{a_i-a_{i+1}}{a_i} < H_m$

Question

For decreasing positive integers $a_1>a_2>...>a_n>0$ when $a_1=m$.

Mark $a_{n+1}=0$, Prove that $\sum_{k=1}^n \frac{a_i-a_{i+1}}{a_i} < H_m=\sum_{k=1}^m \frac{1}{k}$

Might add that $n$ can be chosen by us, as long as $a_1=m$.

I got the problem from a different problem and if I prove this I solved the problem, so I'm not sure if it's true.

I know the harmonic number is achieved if we choose $a_i=m-i+1$ i.e $a_m=1<a_{m-1}=2<...<a_1=m$

My attemp was to prove that the question is equivalent to proving $$\min \sum_{k=1}^n \frac{a_{i+1}}{a_i} $$ is achieved by $a_i=m-i+1$ i.e $a_m=1<a_{m-1}=2<...<a_1=m$.

Showing the equivalent is simple, but proving that this is the best I havn't manage to do.

Answer 1

The idea has been nicely demonstrated in Matija's answer. Here is a formal proof for the general case.

For $1 \le i \le n$ and $a_{i+1}+1 < k \le a_i$ is $1/a_i \le 1/k$, so we have $$ \frac{a_i - a_{i+1}}{a_i} = \sum_{k=a_{i+1}+1}^{a_i} \frac 1{a_i} \le \sum_{k=a_{i+1}+1}^{a_i} \frac 1k \, , $$ with equality if $a_i - a_{i+1} = 1$, and strict inequality otherwise.

It follows that $$ \sum_{i=1}^n \frac{a_i - a_{i+1}}{a_i} \le \sum_{i=1}^n \sum_{k=a_{i+1}+1}^{a_i} \frac 1k \overset{(*)}{=} \sum_{k=1}^m \frac 1k = H_m \, . $$ $(*)$ holds because every integer $k$ between $1$ and $m$ is in exactly one half-open interval $(a_{i+1}, a_i]$.

Equality holds if $a_i - a_{i+1} = 1$ for all $i$, that is if $n = m$ and $a_i = m+1-i$ for $1 \le i \le m$. Otherwise the inequality is strict.

Answer 2

A formal proof is a bit challenging to write and to read, so here's an example. Say we have $a_1=8$, $a_2=5$ and $a_3=1$. This gives us $m=8$ and $n=3$. So, we consider the sum \begin{align*}S&=\sum_{i=1}^{3}\frac{a_i-a_{i+1}}{a_i}\\&=\frac{8-5}8+\frac{5-1}5+\frac{1-0}1\\&=\frac38+\frac45+\frac11.\end{align*} Now, we rewrite the fractions to obtain ones in the numerators, yielding \begin{align*}S&= \frac18+\frac18+\frac18+\frac15+\frac15+\frac15+\frac15+\frac11\\ &<\frac18+\frac17+\frac16+\frac15+\frac14+\frac13+\frac12+\frac11\\&=H_8. \end{align*} I hope this helps to establish the general case.