116 Given the sequence $\left\{a_{n}\right\}$ where $a_{1}=\frac{1}{2}$, and $a_{n+1}=\frac{1}{2} a_{n}+\frac{2 n+3}{2^{n+1}}\left(n \in \mathbf{N}^{*}\right)$,
(1) Find the general term formula of the sequence $\left\{a_{n}\right\}$;
(2) Find the sum of the first $n$ terms $S_{n}$ of the sequence $\left\{a_{n}\right\}$.
16 (1) Since $a_{n+1}=\frac{1}{2} a_{n}+\frac{2 n+3}{2^{n+1}}$,
we have
$$
2^{n+1} a_{n+1}=2^{n} a_{n}+2 n+3,
$$

Let $b_{n}=2^{n} a_{n}$, then $b_{1}=1$ and $b_{n+1}=b_{n}+2 n+3$,
so
$$
\begin{aligned}
b_{n} & =\left(b_{n}-b_{n-1}\right)+\left(b_{n-1}-b_{n-2}\right)+\cdots+\left(b_{2}-b_{1}\right)+b_{1} \\
& =(2 n+1)+(2 n-1)+\cdots+5+1 \\
& =\frac{1+(2 n+1)}{2}(n+1)-3 \\
& =n^{2}+2 n-2, \\
a_{n} & =\frac{n^{2}+2 n-2}{2^{n}} .
\end{aligned}
$$
(2)
$$
\begin{aligned}
S_{n} & =\sum_{k=1}^{n} a_{k} \\
& =\sum_{k=1}^{n} \frac{k^{2}+2 k-2}{2^{k}} \\
& =\sum_{k=1}^{n} \frac{k^{2}}{2^{k}}+2 \sum_{k=1}^{n} \frac{k}{2^{k}}-2 \sum_{k=1}^{n} \frac{1}{2^{k}} .
\end{aligned}
$$

Let $P_{n}=\sum_{k=1}^{n} \frac{k^{2}}{2^{k}}$, then
$$
\begin{aligned}
\frac{1}{2} P_{n} & =P_{n}-\frac{1}{2} P_{n} \\
& =\sum_{k=1}^{n} \frac{k^{2}}{2^{k}}-\frac{1}{2} \sum_{k=1}^{n} \frac{k^{2}}{2^{k}} \\
& =\sum_{k=1}^{n} \frac{2 k-1}{2^{k}}-\frac{n^{2}}{2^{n+1}},
\end{aligned}
$$

so
$$
\frac{1}{2} P_{n}=\sum_{k=1}^{n} \frac{2 k-1}{2^{k}}-\frac{n^{2}}{2^{n+1}},
$$

thus
$$
\begin{aligned}
\frac{1}{4} P_{n} & =\frac{1}{2} P_{n}-\frac{1}{4} P_{n} \\
& =\frac{1}{2}+\frac{2}{2^{2}}+\frac{2}{2^{3}}+\cdots+\frac{2}{2^{n}}-\frac{2 n-1}{2^{n+1}}-\frac{n^{2}}{2^{n+2}} \\
& =\frac{3}{2}-\frac{1}{2^{n-1}}-\frac{2 n-1}{2^{n+1}}-\frac{n^{2}}{2^{n+2}},
\end{aligned}
$$

so
$$
P_{n}=6-\frac{4}{2^{n-1}}-\frac{2 n-1}{2^{n-1}}-\frac{n^{2}}{2^{n}} .
$$

Using the method of differences, we get
$$
\sum_{k=1}^{n} \frac{k}{2^{k}}=2-\frac{1}{2^{n-1}}-\frac{n}{2^{n}},
$$

and $\sum_{k=1}^{n} \frac{1}{2^{k}}=1-\frac{1}{2^{n}}$, thus
$$
\begin{aligned}
S_{n} & =6-\frac{4}{2^{n-1}}-\frac{2 n-1}{2^{n-1}}-\frac{n^{2}}{2^{n}}+2\left(2-\frac{1}{2^{n-1}}-\frac{n}{2^{n}}\right)-2\left(1-\frac{1}{2^{n}}\right) \\
& =8-\frac{n^{2}+6 n+8}{2^{n}}
\end{aligned}
$$