Let $a_n$ be a sequence of non negative real numbers such that $a_{n+m}\le a_n+a_m$ for all natural numbers $m$ and $n$. Prove that $$a_n\le ma_1+(n/m-1)a_m$$ for all $n\ge m$.

Progress: From the given condition we have $a_n\le na_1$. Hence it suffices to show that $$na_1 \le ma_1+(n/m-1)a_m$$ $$\implies{}ma_1\le a_m.$$ However the reverse is true. So its seems that the given inequality is much stronger than $a_n\le na_1$.


You're right, it is much stronger. If, say, $a_2$ is strictly less than $2a_1$, then that lowers the upper bound on all later terms of the sequence.

Think about the problem intuitively first. Why is it true? Well, the $(\frac{n}{m} - 1)a_m$ is there because instead of adding successive $a_1$'s you can add $a_m$'s over and over, until you would have crossed $n$ - that means you can adding $a_m$ up to $\frac{n}{m}-1$ times. Then there's a little left over - what step size can we use for that part? How many steps could it take?

This is all very vague and based on an intuitive understanding of what's going on - the next step is to wrap it up in the formalism necessary to make a real proof. I'll leave that to you.


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.