Resolver la recurrencia

Question

$T(n) = 2$ Si $n=0$

$T(n) = 9T(n-1)-56n +63$ Si $n>=1$

Sustitución repetida

$k=1$

$T(n) = 9T(n-1)-56n+63 $

$k =2$

$T(n) = 81T(n-2) -560n + 1134$

$k =3$

$T(n) = 729T(n-3) -5096n + 15309$

No puedo encontrar el patrón para el término n y el número entero

Por ahora solo tengo

T(n) = $9^k(n-k)$

Answer 1

Primero encontrar una solución particular que satisface $T(n)=9T(n-1)-56n+63$. Deje que la solución particular a ser

$$T(n)=An+B.$$

Entonces tenemos

$$An+B=9A(n-1)+9B-56n+63.$$

Para que esto Mantenga todos $n$, tenemos $A=7$, $B=0$. Entonces encontrar la solución general de $T(n)=9T(n-1)$, $T(n)=9^nC$. Por lo tanto la solución general del problema es

$$T(n)=7n+9^nC.$$

Para encontrar el $C$ necesitamos la condición inicial $T(1)=2$. Así $C=-5/9$. La solución final es

$$T(n)=7n-5\times 9^{n-1}.$$

Answer 2

Vamos a aplicar funciones de generación. No siempre es el método más fácil, pero sólidamente obras. De $$T_n=9T_{n-1}-56n+63$$ la generación de la función es $$f(x)=\sum\limits_{n=0}T_nx^n \tag{1}$$ $$f(x)=T_0+\sum\limits_{n=1}T_nx^n=T_0+\sum\limits_{n=1}\left(9T_{n-1}-56'n+63\right)x^n=\\ T_0+9\sum\limits_{n=1}T_{n-1}x^n-56\sum\limits_{n=1}nx^n+63\sum\limits_{n=1}x^n=\\ T_0+9x\sum\limits_{n=1}T_{n-1}x^{n-1}-56 x\sum\limits_{n=1}nx^{n-1}+63\sum\limits_{n=1}x^n=\\ T_0+9xf(x)-\frac{56 x}{(1-x)^2}+\frac{63x}{1-x}$$ O $$f(x)=T_0+9xf(x)-\frac{56x}{(1-x)^2}+\frac{63x}{1-x}$$ $$f(x)=\frac{T_0}{1-9x}-\frac{56x}{(1-9x)(1-x)^2}+\frac{63x}{(1-9x)(1-x)}$$ $$f(x)=\frac{T_0}{1-9 x} +\frac{7}{(1 - x)^2} + \frac{7}{8(1 - x)} - \frac{63}{8(1 - 9x)} -\frac{63}{8(1 - x)} + \frac{63}{8(1 - 9x)}=\\ f(x)=\frac{T_0}{1-9 x} +\frac{7}{(1-x)^2} -\frac{7}{1-x}$$

$$f(x)=T_0\sum\limits_{n=0}(9x)^n+7\sum\limits_{n=0}(n+1)x^n-7\sum\limits_{n=0}x^n=\sum\limits_{n=0}\left(T_0\cdot 9^n +7n \right)x^n \tag{2}$$ O, comparando los términos de $(1)$ $(2)$ $$T_n=T_0\cdot 9^n +7n$$ Algunos de los accesos directos se explican aquí.

El paso final es encontrar a $T_0$ ...

• de $\color{red}{2=T_0\cdot9+7}$, determinado $T(n)=2$ si $n=1$, esta fue la pregunta original, como por la edición de la historia. O
• de $\color{red}{2=T_0}$, determinado $T(n)=2$ si $n=0$, esto es a partir de la actualización de la pregunta, como por la edición de la historia.

Esto demuestra la flexibilidad de las funciones de generación de ...

Answer 3

Aquí le damos una solución más simple, que le doy por la forma generalizada

$$Tn=AT{n-1}+Bn+C,\quad T_0 \text{ given}$$

Que $T_n=f_n+pn+q$, entonces

$$\begin{align} & {{f}{n}}=A{{f}{n-1}}+n\left( Ap+B-p \right)+\left( -Ap+Aq-q \right) \ \ & \text{Let} \ & p=-\frac{B}{A-1};\quad q=-\frac{pA-C}{A-1} \ & f{n}=A{{f}{n-1}} \ & f_n=f_0A^n,\quad f_0=T_0+q\ \ & T_n=f_0A^n+pn+q \end {Alinee el} $$

En el presente caso, con $[A,B,C]=[9,-56,63]$, encontramos que el $[p,q,f_0]=[7,0,2]$ para que

$$T_n=2\cdot 9^n +7n$$

Yo he verificado esta solución numéricamente.