¿Cómo resuelvo una relación de recurrencia cuando la ecuación característica tiene menos raíces que términos?

Question

Sé cómo resolver relaciones de recurrencia "simples". Por ejemplo, digamos que tienes

$$c_0 = 20$$ $$c_1 = 30$$ $$c_n = 3 c_{n-1} - 2 c_{n-2}$$

Podemos escribir la ecuación característica como

$$3x^{n-1} - 2x^{n-2} = x^n$$

Resolviendo esto con $n=2$ obtenemos $x = 1$ o $x = 2$ . Esto nos permite escribir la relación $c_n = \alpha_1 1^n + \alpha_2 2^n$ y podemos resolver para $\alpha_1$ y $\alpha_2$ con los estados iniciales $c_0$ y $c_1$ .

Sin embargo, esto depende del hecho de que $3x^{n-1} - 2x^{n-2} = x^n$ tiene dos raíces.

Ahora, estoy atascado en otro problema donde la ecuación característica tiene menos raíces que términos.

Digamos que tengo esta relación de recurrencia en su lugar:

$$a_0 = 0$$ $$a_1 = 2$$ $$a_2 = −1$$ $$a_n = 9a_{n-1} - 15a_{n-2} - 25a_{n-3}$$

La ecuación característica sería:

$$9x^{n-1} - 15x^{n-2} - 25x^{n-3} = x^n$$

Sin embargo, resolver con $n=3$ Sólo obtenemos dos raíces: $x=-1$ o $x=5$ . No hay suficientes raíces para escribir una relación en forma de $a_n = \alpha_1 r_1^n + \alpha_2r_2^n + \alpha_3r_3^n$ . ¿Cómo debo proceder?

Answer 1

La ecuación característica es en realidad $x^3-9x^2+15x+25 = 0$ no depende de $n$ . Después de factorizar esto se convierte en $(x+1)(x-5)^2 = 0$ con un doble raíz en $x=5$ . En este caso la solución general tiene la forma $a_n = \alpha_1(-1)^n + \alpha_2 \cdot 5^n + \alpha_3n \cdot 5^n$ y puede utilizar los valores conocidos de $a_0,a_1,a_2$ para resolver $\alpha_1,\alpha_2,\alpha_3$ .

En general, si $r$ es una raíz de la ecuación característica de multiplicidad $m$ da lugar a estos $m$ términos en la solución general: $$\alpha_1r^n + \alpha_2nr^n + \alpha_3n^2 r^n + \dots + \alpha_m n^{m-1}r^n.$$ Así, siempre tendrá tantos términos como el grado de la ecuación característica.

Answer 2

Factorizar el polinomio característico para obtener $$x^3-9x^2+15x+25=(x+1)(x-5)^2$$ El $x+1$ requiere un término de la forma $a(-1)^k$ pero el $(x-5)^2$ el término requiere $(b+ck)5^k$ . Esto se debe a que ambos $5^k$ y $k\:5^k$ son aniquilados por el operador de diferencia $(\Delta-5)^2$ . Ahora, sólo hay que encontrar $a$ , $b$ y $c$ para ajustarse a sus datos iniciales.

Para los factores de $(x-a)^n$ Utilizar $(b_0+b_1 k+b_2 k^2+...+b_{n-1}k^{n-1})a^k$ ya que éste es aniquilado por $(\Delta-a)^n$ .

Answer 3

$\newcommand{\+}{^{\dagger}} \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{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ Siempre se puede insertar un parámetro $\ds{\epsilon}$ para "eliminar" la igualdad de las raíces. Al final, toma un límite adecuado para restaurar la recurrencia original. Para ilustrar el método resolveré el sencillo ejemplo $$a_{n + 1} - 2a_{n} + a_{n - 1} = 0\qquad\mbox{with}\qquad a_{0} = 0\,,\quad a_{1} = 1$$ La solución es, por supuesto, $\color{#66f}{\LARGE \ds{a_{n} = n}}$ y la "ecuación característica" tiene la raíz doble igual a uno.

En su lugar, resolveré $\ds{a_{n + 1} - 2a_{n} + \epsilon a_{n - 1} = 0}$ . La "ecuación característica" tiene raíces $\ds{r_{\pm} = 1 \pm \underbrace{\root{1 - \epsilon^{2}}}_{\ds{\equiv \delta}}}$ \begin {align} a_{n}&= Ar_{-}^{n} + Br_{+}^{n} \quad\imp\quad A + B = 0\,, \quad Ar_{-} + Br_{+} = 1 \quad\imp\quad \left\lbrace\begin {array}{rcl} A & = & {1 \over r_{-} - r_{+}} \\ B & = & -A \end {array} \right. \\ [3mm] a_{n} &={r_{-}^{n} - r_{+}^{n} \over r_{-} - r_{+}} \end {align}

El límite $\ds{\epsilon \to 1}$ rendimientos: $$\lim_{\epsilon \to 1}{r_{-}^{n} - r_{+}^{n} \over r_{-} - r_{+}} =\lim_{\delta \to 0}{\pars{1 - \delta}^{n} - \pars{1 + \delta}^{n} \over -2\delta} =\lim_{\delta \to 0} {n\pars{1 - \delta}^{n - 1}\pars{-1} - n\pars{1 + \delta}^{n - 1} \over -2} =\color{#66f}{\LARGE n}$$

Answer 4

Utilizar directamente la función generadora: definir $A(z) = \sum_{n \ge 0} a_n z^n$ , escribe la recurrencia sin sustracciones en los índices: $$a_{n + 3} = 9 a_{n + 2} - 15 a_{n + 1} - 25 a_n$$ Multiplicar por $z^n$ y sumar sobre $n \ge 0$ reconocer: $$\sum_{n \ge 0} a_{n + k} z^n = \frac{A(z) - a_0 - a_1 z - \ldots - a_{k - 1} z^{k + 1}}{z^k}$$ para conseguirlo: $$\frac{A(z) - 2 z + z^2}{z^3} = 9 \frac{A(z) - 2 z}{z^2} - 15 \frac{A(z)}{z} - 25 A(z)$$ Escrito como fracciones parciales: $$A(z) = \frac{53}{60 (1 - 5 z)} - \frac{3}{10 (1 - 5 z)^2} - \frac{7}{12 (1 + z)}$$ El teorema del binomio generalizado permite leer los coeficientes: \begin {align} a_n &= \frac {53}{60} \cdot 5^n - \frac {3}{10} \binom {-2}{n} (-5)^n - \frac {7}{12} \cdot (-1)^n \\ &= \frac {53}{60} \cdot 5^n - \frac {3}{10} \binom {n + 2 - 1}{2 - 1} \cdot 5^n - \frac {7}{12} \cdot (-1)^n \\ &= \frac {(35 - 18 n) \cdot 5^n - 35 \cdot (-1)^n}{60} \end {align} Las raíces repetidas dan términos que incluyen $\binom{-m}{n} = \binom{n + m - 1}{m - 1}$ que no es más que un polinomio de grado $m - 1$ en $n$ .