
\begin{problem}
Find an closed-form solution for this recurrence:
%
\begin{align*}
T(1) & = 1 \\
T(n) & = \sum_{i=1}^{n-1} iT(i) & (\text{for $n > 1$})
\end{align*}

\noindent  Hint: Consider $T(n)-(n-1)T(n-1)$.
\end{problem}

\solution{
\begin{align*}
T(2) & = 1\cdot T(1) = 1,\\
T(n)-(n-1)T(n-1) & = \sum_{i=1}^{n-2}{iT(i)} = T(n-1), & \text{for $n >
2$, so}\\
T(n) & = (n-1)T(n-1)+T(n-1) = nT(n-1) & \text{for $n>2$.}
\end{align*}

So we have:
\[
T(n) = \begin{cases}
       1,  & \mbox{for $n=1$;}\\
       n!/2, & \mbox{for $n\geq 2$.}
      \end{cases}
\]

Verify by induction:

{\bf Base case}($n=2$): $T(2)= 1 =2!/2$, as required.

{\bf Inductive step:}
\begin{align*}
T(n+1) &= (n+1)T(n)\\
       &= (n+1)~n!/2 & \mbox{(by ind. hyp.)}\\
       &= (n+1)!/2
\end{align*}
}
