9. The sequence $\left\{a_{n}\right\}$ satisfies: $a_{1}=0, a_{2}=1, a_{n}=\max _{1 \leq i \leq n-1}\left\{a_{i}+a_{n-i}+i\right\}$, find the general term formula of $\left\{a_{n}\right\}$.
【Answer】 $a_{n}=\frac{n(n-1)}{2}$
【Detailed Solution】Using mathematical induction, when $n=1, a_{1}=0$, it fits; assume $n \leq k, a_{n}=\frac{n(n-1)}{2}$, when $n=k+1$, then $a_{k+1}=\max _{1 \leq i \leq k}\left\{a_{i}+a_{{k+1}-i}+i\right\}=\max _{1 \leq i \leq k}\left\{\frac{i(i-1)}{2}+\frac{(k+1-i)(k-i)}{2}+i\right\}$ $=\frac{k^{2}+k}{2}+\max _{1 \leq i \leq k}\{i(i-k)\}=\frac{k^{2}+k}{2}$, hence when $n=k+1$, the proposition holds, so $a_{n}=\frac{n(n-1)}{2}$.