Bounded sequence of reals

Question

Suppose that $\{a_{n} \}$ is a sequence of real numbers that satisfy $a_{i} + a_{j} \geq a_{i+j}$. Then prove $$a_{n} \leq \sum_{i=1}^{n} \frac{a_{i}}{i}$$. I tried to use straight-up induction, but I am getting stuck. What I have is: $a_{n+1} \leq a_{1} + a_{n} \leq a_{1} + \sum_{i=1}^{n} \frac{a_{i}}{i}$, but I don't seem to be getting anywhere.

Answer 1

From the inequality you easily obtain that for all integers $i_1, ..., i_k$, one has: $a_{i_1} + ... + a_{i_k} \geq a_{i_1 + ... + i_k}$. By taking them all equal, one gets: $a_{kl} \leq l \cdot a_k$, so $\frac{a_{kl}}{l} \leq a_k$.

We have: $$ a_1 + a_{n-1} \geq a_n \\ ... \\ a_{n-1} + a_{1} \geq a_n \\ $$

Summing all the inequalities gives $(n-1) \cdot a_n \leq 2\cdot(a_1 + \cdots + a_{n-1})$. Let us use this to prove the induction.

Assume the inequality is true for integers $k \leq n$. We will show it stands for $n+1$.

From what we proved we get $n \cdot a_{n+1} \leq 2\cdot(a_1 + \cdots + a_{n})$.

Thus,

$$ \begin{align*} n \cdot a_{n+1} &\leq 2\cdot \left( a_1 + (a_1 + \frac{a_2}{2}) + \cdots + (a_1 + \cdots + \frac{a_n}{n}) \right) \\ &\leq 2\cdot \left( n \cdot a_1 + (n-1) \cdot \frac{a_2}{2} + \cdots + 1 \cdot \frac{a_n}{n} \right) \\ \end{align*} $$

Adding $a_{n+1}$ on both sides gives:

$$ \begin{align*} (n+1) \cdot a_{n+1} &\leq 2\cdot \left( n \cdot a_1 + (n-1) \cdot \frac{a_2}{2} + \cdots + 1 \cdot \frac{a_n}{n} \right) + a_{n+1} \\ \end{align*} $$

But I do not know how to go further...

Answer 2

As Ted Shifrin suggests, we should try Gauss's trick by considering the following:

$$S=\sum_{i<n}a_i=a_1+a_2+\dots+a_{n-1}$$

By summing it backwards we have:

$$S=a_{n-1}+a_{n-2}+\dots+a_1$$

By adding termwise with itself, we end up with

$$2S=(a_1+a_{n-1})+(a_2+a_{n-2})+\dots+(a_{n-1}+a_1)$$

Applying the given inequality, all of these terms are greater than $a_n$, and there are $n-1$ such terms. Adding one more $a_n$ to both sides, we end up with

$$a_n+2S\ge na_n\tag1$$

On the other hand, we also know, by induction, that we have

$$a_i\le\sum_{j\le i}\frac{a_j}j$$

for all $i<n$. Plugging this into $S$, we have

$$S\le\sum_{i<n}\sum_{j\le i}\frac{a_j}j$$

Rearranging the sums gives us

$$S\le\sum_{j<n}\sum_{j\le i<n}\frac{a_j}j=\sum_{j<n}\frac{n-j}ja_j=-S+n\sum_{j<n}\frac{a_j}j$$

Adding $a_n+S$ to both sides and recall $(1)$ to get

$$na_n\le a_n+2S\le a_n+n\sum_{j<n}\frac{a_j}j$$

Divide both sides by $n$ and we can conclude that

$$a_n\le\frac{a_n}n+\sum_{j<n}\frac{a_j}j=\sum_{j\le n}\frac{a_j}j$$

Hence it holds by induction.

Answer 3

For $n=1$ we have $a_1\leq a_1$.

For $n=2$ we need to prove that $$a_2\leq a_1+\frac{a_2}{2}$$ or $$a_1+a_1\geq a_2.$$ Now, let it be true for any $n\leq k$.

Thus, $$a_1\leq a_1,$$ $$a_2\leq a_1+\frac{a_2}{2},$$ $$.$$ $$.$$ $$.$$ $$a_k\leq a_1+\frac{a_2}{2}+...+\frac{a_k}{k},$$ which after summing gives: $$a_1+a_2+...+a_k\leq ka_1+(k-1)\frac{a_2}{2}+...+\frac{a_k}{k}$$ or $$a_1+ka_1+(k-1)\frac{a_2}{2}+a_2+...+\frac{a_k}{k}+a_k\geq2(a_1+a_2+...+a_k),$$ which gives $$(k+1)\left(a_1+\frac{a_2}{2}+...+\frac{a_k}{k}\right)\geq(a_1+a_k)+(a_2+a_{k-1})+...+(a_k+a_1)\geq ka_{k+1}$$ and from here $$a_1+\frac{a_2}{2}+...+\frac{a_k}{k}\geq\frac{ka_{k+1}}{k+1}$$ or $$a_1+\frac{a_2}{2}+...+\frac{a_k}{k}+\frac{a_{k+1}}{k+1}\geq\frac{ka_{k+1}}{k+1}+\frac{a_{k+1}}{k+1}=a_{k+1}$$ and we are done by induction.