Resolver una ecuación de recurrencia que da polinomios

Question

Estoy intentando resolver la siguiente ecuación de recurrencia:

$$ T(n) = kT(n - 1) + nd $$

He ampliado los 4 primeros valores ( $n = 1$ ):

$$\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}$$

Pude convertir lo anterior en la siguiente suma, con la esperanza de encontrar una solución de forma cerrada:

$$ T(n) = k^{n - 1} + d \sum_{i=1}^{n-1} (i + 1) (k^{n-i-1}) $$

Pero después de este punto estoy atascado. ¿Es correcto crear la suma o hay algo mejor que pueda intentar?

Answer 1

Utilizando \begin{align} \sum_{j=0}^{m} t^{j} = \frac{1-t^{m+1}}{1-t} \end{align} entonces \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} para lo cual \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} Ahora, \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} Esto conduce a \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}

---

Ahora la ecuación de diferencia \begin{align} T(n) = k T(n-1) + n d \end{align} donde $T(1) = 1$ conduce a la solución \begin{align} T(n) = k^{n-1} + d \sum_{j=1}^{n-1} (j+1) k^{n-j-1} \end{align} que puede verse en la forma \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

Puedes convertir tu recursión en una recursión más lineal utilizando la siguiente técnica:

$$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) es sólo una reescritura, (B) es la ecuación para $n-1$ , (C) \= (A) - (B) , (D) es sólo una reescritura.

(D) es bastante estándar, mi método preferido para terminarlo son las 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}$$

Desde $D^n = \begin{bmatrix} k^n & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}$ lo tendrás:

$$ \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}$$

Por fin:

$$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}}$$

Sé que este no es el enfoque con el que empezaste, pero es un enfoque muy general para resolver incluso recurrencias no lineales. Espero que te ayude.