Relaciones de recurrencia Forma cerrada

Question

Entonces, la cuestión es derivar la solución de forma cerrada a la relación de recurrencia $$T(n) = 3T(n-1) + 5,\hspace{5mm} T(0) = 0.$$

$\begin{align}T(n) &= 3T(n-1)+5 \\&= 3(3T(n-2)+5)+5 \\&= 3(3(3T(n-3)+5)+5)+5\end{align}$

Estoy luchando por ir desde aquí. Entiendo que es $3$ al poder de algo pero estoy perdido en lo que tengo que hacer después de esto.

Answer 1

Calcular los primeros valores: $0,5,20,65,200$ dividiendo por $5$ esto es $0,1,4,13,40$ multiplicando por $2$ obtenemos $0,2,8,26,80$ añadiendo $1$ obtenemos $1,3,9,27,81$ . De lo contrario, puede utilizar las funciones de generación:

Dejemos que $A=\sum\limits_{n=0}^\infty t(n)x^n$ .

Entonces $A=3xA+5\sum\limits_{n=1}^\infty x^n$ (ya que $f(0)=0$ ).

Entonces $(1-3x)A=\frac{5}{1-x}-5$ así que $A=\frac{5}{(1-3x)(1-x)}-\frac{5}{1-3x}=\frac{5}{2(x-1)}-\frac{15}{2(3x-1)}+\frac{5}{3x-1}=\frac{5}{2(x-1)}-\frac{5}{2(3x-1)}=\frac{1}{2}(\sum\limits_{n=0}^\infty 5\cdot 3^{n} -5)$

por lo tanto $f(n)=\frac{5(3^{n}-1)}{2}$

Answer 2

Aquí hay dos tipos de soluciones: la homogénea y la particular. Reescribamos la ecuación como

$$T_n - 3 T_{n-1} = 5$$

La solución homogénea es simplemente la solución asumiendo que el RHS es cero. Así, $T_n^{(H)} = A \cdot 3^n$ . La solución particular es una solución simple que satisface la ecuación y las condiciones de contorno. En este caso, $T_n^{(P)} = B$ , una constante:

$$B - 3 B = 5 \implies B=-\frac{5}{2} $$

La solución es la suma de las soluciones homogéneas y particulares:

$$T_n = A \cdot 3^n - \frac{5}{2} $$

$$T(0)=0 \implies A=\frac{5}{2} $$

Answer 3

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ " $\,$ Si $\,$ " hay una solución que es $n$ -independiente debe ser $\ds{\frac{5}{1 - 3} =-\,\frac{5}{2}}$ . Esto significa que $\ds{\,{\rm T}\pars{n} - \pars{-\,\frac{5}{2}}}$ satisface una ecuación de recurrencia homogénea: \begin{align} \,{\rm T}\pars{n} + \frac{5}{2}=3\bracks{\,{\rm T}\pars{n - 1} + \frac{5}{2}} \end{align} Entonces, \begin{align} \,{\rm T}\pars{n} + \frac{5}{2}=3^{1}\bracks{\,{\rm T}\pars{n - 1} + \frac{5}{2}} =3^{2}\bracks{\,{\rm T}\pars{n - 2} + \frac{5}{2}}=\cdots= 3^{n}\bracks{\overbrace{\,{\rm T}\pars{0}}^{\ds{=\ \dsc{0}}} + \frac{5}{2}} =\frac{5}{2}\,3^{n} \end{align} lo que lleva a: $$ \color{#66f}{\large\,{\rm T}\pars{n}} =\color{#66f}{\large\frac{5}{2}\pars{3^{n} - 1}} $$