\problemdata     
{S01-PS5-4}           
{Summations using derivatives}              
{S98-PS5, S01-PS5} 		
{S01 Karger}

\begin{problem}


\begin{problemparts}
\problempart Find a closed form solution for
$\sum_{i=1}^n i^2x^i$.

\solution {
From lecture we know that
\[{\displaystyle \sum_{i=1}^n ix^i} = \frac{x - (n+1)x^{n+1} + nx^{n+2}}{(1-x)^2}.\] 
Differentiating (with respect to $x$) the above expression and
multiplying with $x$ we find that 
\begin{eqnarray*}
{\displaystyle \sum_{i=1}^n i^2x^{i-1}} &=& \frac{1+x-(n+1)^2x^{n}+(2n^2+2n-1)x^{n+1}-n^2x^{n+2}}{(1-x)^3}\\
{\displaystyle \sum_{i=1}^n i^2x^i} &=& \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3}
\end{eqnarray*}
}

\problempart Verify your closed form by induction.

\solution {
Proof by induction. Let $P(n)$ be the statement that 
\[{\displaystyle \sum_{i=1}^n i^2x^i} = \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3}.\]
Base Case. $P(1)$ is true since
\[{\displaystyle \sum_{i=1}^1 i^2x^i} = x = \frac{x+x^2-4x^2+3x^3-x^4}{(1-x)^3}.\]
Inductive Step. Assume $P(n)$ is true. Then
\begin{eqnarray*}
{\displaystyle \sum_{i=1}^{n+1} i^2x^i}
& = & {\displaystyle \sum_{i=1}^n i^2x^i} + (n+1)^2x^{n+1} \\
 & = & \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3} + (n+1)^2x^{n+1} \\
& = & \frac{x+x^2-(n+2)^2x^{n+2}+(2(n+1)^2+2(n+1)-1)x^{n+3}-(n+1)^2x^{n+4}}{(1-x)^3}
\end{eqnarray*}
Thus $P(n+1)$ is true. Hence, $P(n)$ is true for all $n$.
}
\end{problemparts}
              

\end{problem}