How can I solve a recursive equation with a summation notation?
I'm assuming that the recurrence is
$$
T(n) = n + \sum_{k=1}^{n-1} [T(n-k) + T(k)],
$$
with base case $T(1) = 1$.

First, notice that
$$
\begin{align*}
T(n) &amp;= n + [T(n-1) + \cdots + T(1)] + [T(1) + \cdots + T(n-1)] \\ &amp;= n + 2[T(1) + \cdots + T(n-1)].
\end{align*}
$$
Similarly,
$$
T(n-1) = n-1 + 2[T(1) + \cdots + T(n-2)].
$$
Subtracting, we obtain
$$
T(n) - T(n-1) = 1 + 2T(n-1),
$$
and so $T(n) = 1 + 3T(n-1)$. Now let $S(n) = T(n) + 1/2$. Then
$$
S(n) = T(n) + 1/2 = 1+3(S(n-1)-1/2)+1/2 = 3S(n-1).
$$
Since $S(1) = T(1) + 1/2 = 3/2$, we conclude that $S(n) = 3^n/2$, and so
$$
T(n) = \frac{3^n-1}{2}.
$$