A Peculiar Function!

First of all, it is easy to see that $f$ is unique, since the recursion generates a unique sequence. Now we claim the following :

Claim : $f(n)=\frac{n(n-1)}{2}, \hspace{10pt}\forall n\geq 1$

In view of the uniqueness of the solution, it is sufficient to show that the proposed function satisfies the recursion for all $n\geq 1$ . We proceed by induction. The base case holds for $n=1$ . Assume that the claim holds for $n=m, (m \geq 1)$ . We will show that the claim holds for $n=m+1$ .

It is easy to see that the proposed function $f$ is convex. Hence by the property of convexity, we have for all $1\leq j\leq m$ $f(m)-f(m+1-j) \geq f(j)-f(1)$ i.e., $f(m)+f(1)\geq f(j)+f(m+1-j)$ This implies that for all $1\leq j \leq m$ , we have $f(m)+f(1)+m \geq f(j)+f(m+1-j)+j$ Hence, $\max_{1\leq j\leq m} \big(f(j)+f(m+1-j)+j\big) = f(m)+f(1)+m=\frac{m(m+1)}{2}$ Which completes the induction step for $n=m+1$ and we are done proving the claim.