Call a sequence $\left \{ a_n \right \}$, $n \geq 1$, strictly subadditive if it satisfies the inequality $$ a_{n+m} < a_n+a_m $$ for all $m$ and $n$. I am wondering whether it is necessarily true that a positive strictly subadditive sequence satisfies $$ \frac{a_n}{n}>\frac{a_{n+1}}{n+1}. $$ All the examples I've come up with so far satisfy this property (e.g., the functions $\sqrt{n}$, $1$, $n+1$). Any input would be appreciated.
Asked
Active
Viewed 621 times
1 Answers
1
Take $a_1=1,a_2=1/3, a_3=1/2$. Assume that we have constructed the first $n\geq 3$ terms so that $$ a_{n}<a_r+a_s $$ holds for all $r,s\in\mathbb N$ with $r+s=n$. Define $$ a_{n+1}=\min \{(a_r+a_s)/2\in\mathbb R|r+s=n+1\}. $$ This way we inductively construct a strictly subadditive sequence $(a_n)_{n\in\mathbb N}$ with $a_1=1,a_2=1/3,a_3=1/2$. Now, $$ a_3/3=1/6=a_2/2, $$ giving you a counter example.
Edit: Alternatively, you can take $a_1=1,a_2=0,a_3=1/2$ and $a_n=0$ for $n\geq 4$. However, the construction above gives you a strictly positive, strictly subadditive sequence.
Jonas Dahlbæk
- 4,776