<s>[INST] Solving a recurrence equation that yields polynomials I am trying to solve the following recurrence equation:
$$
T(n) = kT(n - 1) + nd
$$
I have expanded the first 4 values ($n = 1$ was given):
$$\begin{align}
T(1) & = 1 \\
T(2) & = kT(2-1) + 2d = k + 2d \\
T(3) & = kT(3-1) + 3d = k(k + 2d) + 3d = k^2 + 2kd + 3d  \\
T(4) & = kT(4-1) + 4d = k(k^2 + 2kd + 3d) + 4d = k^3 + 2k^2d + 3dk + 4d\\
\end{align}$$
I was able to convert the above into the following summation, in hopes of finding a closed-form solution:
$$
T(n) = k^{n - 1} + d \sum_{i=1}^{n-1} (i + 1) (k^{n-i-1})
$$
But after this point I am stuck. Was creating the summation the correct thing to do, or is there something better I could try?
 [/INST] You can convert your recursion into a more linear recursion using the following technique:
$$T(n) = k~T(n-1) + n~d$$
$$\frac 1d ~ T(n) - \frac 1d~k~T(n-1) = n \tag{A}$$
$$\frac 1d ~ T(n - 1) - \frac 1d~k~T(n-2) = n - 1 \tag{B}$$
$$\frac 1d ~ T(n) + \left(-k~\frac 1d - \frac 1d\right)~ T(n - 1) + \frac 1d~k~T(n-2) = 1 \tag{C}$$
$$T(n) = (k + 1)~ T(n - 1) - k~T(n-2) + d \tag{D}$$
(A) is just a rewrite, (B) is the equation for $n-1$, (C) = (A) - (B), (D) is just a rewrite.
(D) is pretty standard form, my preferred approach to finishing it is matrices:
$$
\begin{bmatrix}T(n + 2) \\ T(n + 1) \\ 1\end{bmatrix} = 
\begin{bmatrix} 
k+1 & -k & d \\
1 & 0 & 0 \\
0 & 0 & 1 \end{bmatrix}
\begin{bmatrix} T(n + 1) \\ T(n) \\ 1\end{bmatrix}$$
$$
\begin{bmatrix}T(n + 2) \\ T(n + 1) \\ 1\end{bmatrix} = 
\begin{bmatrix} 
k+1 & -k & d \\
1 & 0 & 0 \\
0 & 0 & 1 \end{bmatrix} ^n
\begin{bmatrix} T(1) \\ T(0) \\ 1\end{bmatrix}$$
Jordan Decomp:
$$P = \begin{bmatrix}
1 & 1 & 1 \\
\frac 1k & 1 & 0 \\
0 & 0 & \frac{1-k}d
\end{bmatrix}, D = \begin{bmatrix}
k & 0 & 0 \\
0 & 1 & 1 \\
0 & 0 & 1
\end{bmatrix}$$
$$
\begin{bmatrix}T(n + 2) \\ T(n + 1) \\ 1\end{bmatrix} = \left(P~D~P^{-1}\right)^n
\begin{bmatrix} T(1) \\ T(0) \\ 1\end{bmatrix} = \left(P~D^n~P^{-1}\right)
\begin{bmatrix} T(1) \\ T(0) \\ 1\end{bmatrix}$$
Since $D^n = \begin{bmatrix}
k^n & 0 & 0 \\
0 & 1 & 1 \\
0 & 0 & 1 \end{bmatrix}$, you get:
$$
\begin{bmatrix}T(n + 2) \\ T(n + 1) \\ 1\end{bmatrix} = 
\begin{bmatrix}\frac{{k}^{n+1}-1}{k-1} & -\frac{k\,\left( {k}^{n}-1\right) }{k-1} & \frac{d\,\left( {k}^{n+1}-2\,k+1\right) }{{\left( k-1\right) }^{2}} \\ \frac{{k}^{n}-1}{k-1} & -\frac{{k}^{n}-k}{k-1} & \frac{d\,\left( {k}^{n}-k\right) }{{\left( k-1\right) }^{2}} \\ 0 & 0 & 1\end{bmatrix}
\begin{bmatrix} T(1) \\ T(0) \\ 1\end{bmatrix}$$
Finally:
$$T(n+1) = \frac{{k}^{n}-1}{k-1} ~T(1)  -\frac{{k}^{n}-k}{k-1} ~T(0) + \frac{d\,\left( {k}^{n}-k\right) }{{\left( k-1\right) }^{2}}$$
I know this isn't the approach that you started with, but it is a very general approach to solving even non-linear recurrences.  Hope it helps you.
</s>