China Southeastern Mathematical Olympiad

Divide the recursion formula by $2^{n+1}$ throughout, we obtain
$$\frac{a_{n+1}}{2^{n+1}} = \frac{a_n}{2^n} + \frac{n}{2^{n+1}} + \frac{n}{2},$$
that is,
$$\frac{a_{n+1}}{2^{n+1}} - \frac{a_n}{2^n} = \frac{n}{2^{n+1}} + \frac{n}{2}.$$
Then
$$\sum_{i=1}^n \left( \frac{a_{i+1}}{2^{i+1}} - \frac{a_i}{2^i} \right) = \sum_{i=1}^n \frac{i}{2^{i+1}} + \sum_{i=1}^n \frac{i}{2},$$
$$\frac{a_{n+1}}{2^{n+1}} - \frac{a_1}{2^1} = \frac{n(n+1)}{4} + \sum_{i=1}^n \frac{i}{2^{i+1}},$$
$$a_{n+1} = 2^{n+1} \left[ \frac{n(n+1)}{4} + \frac{1}{2^n} + \frac{1}{2} \sum_{i=1}^n \frac{i}{2^i} \right].$$
Set $S_n = \sum_{i=1}^n \frac{i}{2^i}$, then $2S_n = \sum_{i=1}^n \frac{i}{2^{i-1}}$, and
$$\begin{align*} S_n &= 2S_n - S_n = \sum_{i=1}^n \frac{i}{2^{i-1}} - \sum_{i=1}^n \frac{i}{2^i} \\ &= \sum_{i=1}^n \frac{i}{2^{i-1}} - \sum_{i=2}^{n+1} \frac{i-1}{2^{i-1}} \\ &= \frac{1}{2^{1-1}} - \frac{n+1-1}{2^{n+1-1}} + \sum_{i=2}^n \left( \frac{i}{2^{i-1}} - \frac{i-1}{2^{i-1}} \right) \\ &= 1 - \frac{n}{2^n} + \sum_{i=2}^n \frac{1}{2^{i-1}} \end{align*}$$
$$\begin{aligned} &= 1 - \frac{n}{2^n} + \frac{1}{2} \left[ 1 - \left( \frac{1}{2} \right)^{n-1} \right] \\ &= 1 - \frac{n}{2^n} + 1 - \frac{1}{2^{n-1}} \\ &= 2 - \frac{n+2}{2^n}. \end{aligned}$$
Thus,
$$\begin{aligned} a_{n+1} &= \left[ \frac{n(n+1)}{4} + \frac{1}{2^n} + \frac{1}{2} \left( 2 - \frac{n+2}{2^n} \right) \right] \\ &= 2^{n+1} \left[ \frac{3}{2} + \frac{n(n+1)}{4} - \frac{n+2}{2^{n+1}} \right] \quad (n \ge 1). \end{aligned}$$
Consequently,
$$a_n = 2^{n-2}(n^2 - n + 6) - n - 1 \quad (n \ge 2).$$