XVIII OBM

The upper bound follows by induction. Let $S_m$ be the statement that $f(n)\le 5{\log }_{3}n$ for $n\le 3m+2$. We have $2=1+1$, $3=1+1+1$, $4=1+1+1+1$, $5=1+1+1+1+1$, so $f(2)=2$, $f(3)=3$, $f(4)=4$, $f(5)=5$. We have $1={\log }_{3}3<{\log }_{3}4<{\log }_{3}5$, so $f(3)<5{\log }_{3}3$, $f(4)<5{\log }_{3}4$ and $f(5)<5{\log }_{3}5$. Also $2^4=16>3^2$, so $2<{\log }_3{2}^4=4{\log }_{3}2$. Hence $5{\log }_{3}2>4{\log }_{3}2>2=f(2)$. So $S_1$ is true. Suppose $S_m$ is true. We have $3m+3=(1+1+1)\times (m+1)$, so $f(3m+3)\le 3+f(m+1)=3+5{\log }_3(m+1)<5(1+{\log }_3(m+1))=5{\log }_3(3m+3)$. Similarly, since $3m+4=1+(3m+3)$, we have $f(3m+4)\le 4+f(m+1)<5{\log }_3(3m+3)<5{\log }_3(3m+4)$. Similarly, $f(3m+5)\le 5+f(m+1)\le 5+5{\log }_3(m+1)=5{\log }_3(3m+3)<5{\log }_3(3m+5)$. So $S_{m+1}$ is true. So $S_m$ is true for all $m$.

Induction also works for the lower bound. In any expression for $n$ using $1$s we either have $n=a+b$, with further expressions for $a$ and $b$, or we have $n=a\cdot b$ with further expressions for $a$ and $b$. In the first case if $a=1$, we have to show that $1+{\log }_{3}b\ge {\log }_3(b+1)$, but that is almost obvious since $1+{\log }_{3}b={\log }_3(3b)>{\log }_3(b+1)$. If $a,b>1$, then we have to show that ${\log }_{3}a+{\log }_{3}b\ge {\log }_3(a+b)$, which is again obvious, since if $a\ge b\ge 2$ we have ${\log }_{3}a+{\log }_{3}b={\log }_3(ab)\ge {\log }_3(2a)\ge {\log }_3(a+b)$. In the second case we can assume that $a,b>1$ (since there is no benefit in the expression if $a=1$ or $b=1$), so we have to show that ${\log }_{3}a+{\log }_{3}b\ge {\log }_3(ab)$ which is true (we have equality). So all we need are the starting cases. For $n=2$, it is clear that $f(2)=2$, but $8<9$, so ${\log }_{3}8<{\log }_{3}9$ or $3{\log }_{3}2<2=f(2)$, as required.