Relación de recurrencia de primer orden

Question

Tengo que resolver esta relación: $$a_1 = k \\ a_n = \frac{10}{9} a_{n-1} + k + 1 - n$$ (k es constante)

¿Cómo puedo hacerlo?

Answer 1

Utilice la función generadora $A(x) = \sum_{n \ge 1}a_nx^n$ para capturar la secuencia $\{a_n\}$ .

Nos dan (después de ajustar los índices $n \rightarrow n + 1$ ) $$a_{n+1} = \frac{10}{9}a_n + k - n \text{ for } n \ge 1$$

Multiplicar por $x^n$ en todo y suma para todo valores de $n$ para el que se cumple la recurrencia.

$\begin{eqnarray}&\sum_{n \ge 1}a_{n+1}x^n &= \frac{10}{9}\sum_{n \ge 1}a_{n}x^n + k\sum_{n \ge 1}x^n - \sum_{n \ge 1}nx^n\\\implies&\frac{A(x) - a_1x}{x} &=\frac{10}{9}A(x) + k\frac{x}{1-x} - \frac{x^2}{(1-x)^2} - \frac{x}{1-x}\\\implies&\frac{9 - 10x}{9x}A(x) &= k + (k-1)\frac{x}{1-x} - \frac{x^2}{(1-x)^2}\\\implies &A(x) &=\frac{9kx}{9-10x} + \frac{9(k-1)x^2}{(1-x)(9-10x)} - \frac{9x^3}{(1-x)^2(9-10x)}\end{eqnarray}$

Descomposición de la fracción parcial da

$$A(x) = \frac{81(k-9)}{9-10x} + \frac{9(8-k)}{1-x} +\frac{9}{(1-x)^2}$$

Por lo tanto, tenemos,

$$\begin{align}a_n &= [x^n]A(x)\\&=[x^n]\frac{81(k-9)}{9-10x} + [x^n]\frac{9(8-k)}{1-x} +[x^n]\frac{9}{(1-x)^2}\\&=9(k-9)\left(\frac{10}{9}\right)^n + 9(8-k) + 9(n+1)\end{align}$$

Nota:

• El coeficiente de $x^n$ en $\frac{c}{(1-\alpha x)^m} = c\binom{-m}{n}\alpha^n = c\binom{m + n - 1}{n}\alpha^n$
• La suma $\sum_{n \ge 1}nx^n = x\sum_{n \ge 1}nx^{n-1} = x\frac{d}{dx}\sum_{n \ge 1}x^n = x\frac{d}{dx}(\frac{x}{1-x})$

Answer 2

Pista: escribe la expresión para el siguiente término: $$ a_{n+1} = \frac{10}{9} a_n +k+1 -(n+1) $$ y restar. Entonces el $n$ se cancelará, y podrás construir una ecuación de diferencia, $\Delta a_{n+1} = a_{n+1} - a_{n}$ . ¿Puedes manejar desde aquí?

EDIT: deberías obtener una expresión de la forma $$ \Delta a_{k+1} = r \Delta a_{k} + \gamma $$ donde $r, \ \gamma$ son constantes. Ahora $$ \Delta a_{k+1} = r \Delta a_{k} + \gamma = r^2 \Delta a_{k-1} + r \gamma + \gamma = r^3 \Delta a_{k-2} + r^2 \gamma + r \gamma + \gamma\\ =\ldots = r^{k-1} \Delta a_2 + \Gamma $$ aquí $\Gamma, \Delta a_2$ son constantes que puedes encontrar fácilmente (pista: series geométricas). Ahora suma sobre $k$ en ambos lados. En el LSH tiene una suma telescópica, en el RHS $r^k$ (pista: suma geométrica de nuevo). Sin embargo, ten cuidado con el álgebra.