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{array}{rl}{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{array}$$ $$\begin{array}{rl}& =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{array}$$ Thus, $$\begin{array}{rl}{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](n\ge 1).\end{array}$$ Consequently, $$a_n=2^{n-2}(n^2-n+6)-n-1(n\ge 2).$$