Solving a recurrence equation that yields polynomials

Question

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?

Answer 1

Using \begin{align} \sum_{j=0}^{m} t^{j} = \frac{1-t^{m+1}}{1-t} \end{align} then \begin{align} \sum_{j=0}^{m} j \, t^{j} = \frac{t - (m+1) t^{m+1} + m t^{m+2}}{(1-t)^{2}} \end{align} for which \begin{align} \sum_{j=0}^{m} (j+1) \, t^{j} &= \frac{1}{(1-t)^{2}} \left[ (1-t)(1-t^{m+1}) + t - (m+1) t^{m+1} + m t^{m+2} \right] \\ &= \frac{1}{(1-t)^{2}} \left[ 1 - (m+2) t^{m+1} + (m+1) t^{m+2} \right]. \end{align} Now, \begin{align} \sum_{j=1}^{m} (j+1) t^{j} = \frac{1}{(1-t)^{2}} \left[ 1 - (m+2) t^{m+1} + (m+1) t^{m+2} \right] - 1. \end{align} This leads to \begin{align} \sum_{j=1}^{m} (j+1) t^{m-j} = \frac{1}{(1-t)^{2}} \left[ t^{m} - (m+2) t + (m+1) \right] - t^{m}. \end{align}

---

Now for the difference equation \begin{align} T(n) = k T(n-1) + n d \end{align} where $T(1) = 1$ leads to the solution \begin{align} T(n) = k^{n-1} + d \sum_{j=1}^{n-1} (j+1) k^{n-j-1} \end{align} which can be seen in the form \begin{align} T(n) &= (1-d) k^{n-1} + \frac{d}{(1-k)^{2}} \left[ k^{n-1} - (n+1) k + n \right] \end{align}

Answer 2

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.