Cómo encontrar la fórmula explícita para dos repeticiones?

Question

Tengo que encontrar la solución explícita de dos entrelazamiento recursiones

$$\begin{align} f(n)&=f(n-2)+2g(n-1) \\ g(n)&=g(n-2)+f(n-1) \end{align}$$

para $f(0)=1, f(1)=0, g(0)=0 ,g(1)=1$.

¿Qué técnicas se utilizan comúnmente para este tipo de problema? Gracias!

Answer 1

Sugerencia: podemos escribir esta recurrencia en forma matricial como $$\begin{pmatrix} f(n+1) \\g(n+1) \\f(n) \\g(n) \end{pmatrix} = \begin{pmatrix} 0&2&1&0\\1&0&0&1\\1&0&0&0\\ 0&1&0&0 \end{pmatrix} \begin{pmatrix} f(n) \\g(n) \\f(n-1) \\g(n-1) \end{pmatrix}$$ o más sucinta $\Phi(n)=A\Phi(n-1)$. De esto podemos observar que el $\Phi(n)=A^n \Phi(0)$ donde $\Phi(0)=(0,1,1,0)^T$. Por lo tanto, este ha sido convertido en un problema de álgebra lineal.

Answer 2

Usted puede escribir $$f(n)=f(n-2)+2g(n-1)\\g(n)=g(n-2)+f(n-1)\\ g(n+1)=g(n-1)+f(n)\\g(n-1)=g(n-3)+f(n-2)\\g(n+1)-g(n-1)=g(n-1)-g(n-3)+f(n)-f(n-2)\\g(n+1)-g(n-1)=g(n-1)-g(n-3)+2g(n-1)\\g(n+1)=4g(n-1)-g(n-3)$$ Y usted tiene una sola de recurrencia

Answer 3

$\newcommand{\ángulos}[1]{\left\langle{#1}\right\rangle} \newcommand{\llaves}[1]{\left\lbrace{#1}\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack{#1}\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\mitad}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left({#1}\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert{#1}\right\vert}$

$\ds{% \a la izquierda.\begin{array}{rcl} \ds{\mathrm{f}\pars{n}} & \ds{=} & \ds{\mathrm{f}\pars{n - 2} + 2\mathrm{g}\pars{n-1}} \\[1mm] \ds{\mathrm{g}\pars{n}} & \ds{=} & \ds{\mathrm{g}\pars{n - 2} +\mathrm{f}\pars{n - 1}} \end{array}\right\rbrace \quad\mbox{y}\quad \left\lbrace\begin{array}{rclrcl} \mathrm{f}\pars{0} & \ds{=} & \ds{1,} & \ds{\mathrm{f}\pars{1}} & \ds{=} & \ds{0} \\[1mm] \mathrm{g}\pars{0} & \ds{=} & \ds{0,} & \ds{\mathrm{g}\pars{1}} & \ds{=} & \ds{1} \end{array}\right.}$

---

Con $\ds{\mathbf{u}\pars{n} \equiv {\mathrm{f}\pars{n} \elegir \mathrm{g}\pars{n}}}$: \begin{align} \mathbf{u}\pars{n} & = \pars{\begin{array}{cc}\ds{0} & \ds{2}\\ \ds{1} & \ds{0} \end{array}}\mathbf{u}\pars{n - 1} + \pars{\begin{array}{cc}\ds{1} & \ds{0}\\ \ds{0} & \ds{1}\end{array}}\mathbf{u}\pars{n - 2}\,,\qquad \left\lbrace\begin{array}{rcl} \ds{\mathbf{u}\pars{0}} & \ds{=} & \ds{1 \choose 0} \\[1mm] \ds{\mathbf{u}\pars{1}} & \ds{=} & \ds{0 \choose 1} \end{array}\right. \\[3 mm] & = \bracks{% {3 \over 2}\pars{\begin{array}{cc}\ds{0} & \ds{1}\\ \ds{1} & \ds{0} \end{array}} + \media\,\ic\pars{\begin{array}{cc}\ds{0} & \ds{-\ic}\\ \ds{\ic} & \ds{0} \end{array}}}\mathbf{u}\pars{n - 1} + \pars{\begin{array}{cc}\ds{1} & \ds{0}\\ \ds{0} & \ds{1}\end{array}}\mathbf{u}\pars{n - 2} \end{align}

---

\begin{align} \mathbf{u}\pars{n} & = \vec{a}\cdot\vec{\sigma}\,\,\mathbf{u}\pars{n - 1} + \mathbf{u}\pars{n - 2}\,,\quad \vec{a}\cdot\vec{\sigma} = \pars{\begin{array}{cc}\ds{0} & \ds{2}\\ \ds{1} & \ds{0} \end{array}}\,,\quad \left\lbrace\begin{array}{rcl} \ds{\vec{a}\cdot\vec{\sigma}\,\mathbf{u}\pars{0}} & \ds{=} & \ds{\mathbf{u}\pars{1}} \\[1mm] \ds{\vec{a}\cdot\vec{\sigma}\,\mathbf{u}\pars{1}} & \ds{=} & \ds{2\mathbf{u}\pars{0}} \end{array}\right. \end{align} donde $\ds{\vec{a} \equiv {3 \over 2}\,\hat{x} + \half\,\ic\,\hat{y}}$ $\ds{\braces{\sigma_{i}\ \mid\ i = 0,x,y,z}}$ son las Matrices de Pauli. A continuación, \begin{align} \sum_{n = 2}^{\infty}\mathbf{u}\pars{n}z^{n} & = \vec{a}\cdot\vec{\sigma}\sum_{n = 2}^{\infty}\mathbf{u}\pars{n - 1}z^{n} + \sum_{n = 2}^{\infty}\mathbf{u}\pars{n - 2}z^{n} \\[3mm] \sum_{n = 0}^{\infty}\mathbf{u}\pars{n}z^{n} - \mathbf{u}\pars{0} - \mathbf{u}\pars{1}z & = \vec{a}\cdot\vec{\sigma}\,z \bracks{\sum_{n = 0}^{\infty}\mathbf{u}\pars{n}z^{n} - \mathbf{u}\pars{0}} + z^{2}\sum_{n = 0}^{\infty}\mathbf{u}\pars{n}z^{n} \end{align} lo que conduce a $$ \bracks{\pars{1 - z^{2}}\sigma_{0} - \vec{a}\cdot\vec{\sigma}\,z} \sum_{n = 0}^{\infty}\mathbf{u}\pars{n}z^{n} = \bracks{\sigma_{0} - \vec{a}\cdot\vec{\sigma}\,z}\mathbf{u}\pars{0} + z\mathbf{u}\pars{1} = \mathbf{u}\pars{0} $$ Multiplicar ambos lados, por la izquierda, con la matriz $\ds{\bracks{\pars{1 - z^{2}}\sigma_{0} + \vec{a}\cdot\vec{\sigma}\,z}}$ $\ds{\pars{~\mbox{note that}\ \pars{\vec{a}\cdot\vec{\sigma}}^{2} = \vec{a}\cdot\vec{a} = 2~}}$: \begin{align} \bracks{\pars{1 - z^{2}}^{2} - 2z^{2}} \sum_{n = 0}^{\infty}\mathbf{u}\pars{n}z^{n} & = \bracks{\pars{1 - z^{2}}\sigma_{0} + \vec{a}\cdot\vec{\sigma}\,z} \mathbf{u}\pars{0} = \pars{1 - z^{2}}\mathbf{u}\pars{0} + z\,\mathbf{u}\pars{1} \end{align}

---

\begin{align} \imp\quad\sum_{n = 0}^{\infty}\mathbf{u}\pars{n}z^{n} & = {\pars{1 - z^{2}}\mathbf{u}\pars{0} + z\,\mathbf{u}\pars{1} \over z^{4} - 4z^{2} + 1} \\[3mm] \iff\quad & \left\lbrace\begin{array}{rcl} \ds{\mathrm{f}\pars{n}} & \ds{=} & \ds{\bracks{z^{n}}\pars{{1 - z^{2} \over z^{4} - 4z^{2} + 1}}} \\[1mm] \ds{\mathrm{g}\pars{n}} & \ds{=} & \ds{\bracks{z^{n}}\pars{{z \over z^{4} - 4z^{2} + 1}}} \end{array}\right. \end{align}

Los ceros de $\ds{w^{2} - 4w + 1 = 0}$ están dadas por $\ds{r_{\pm} = 2 \pm \root{3}}$ $\ds{r_{-} \approx 0.2679}$ y $\ds{r_{+} = 1/r_{-} \approx 3.7321}$ tal que \begin{align} {1 \over z^{4} - 4z^{2} + 1} & = {1 \over \pars{z^{2} - r_{-}}\pars{z^{2} - r_{+}}} = {1 \over r_{+} - r_{-}}\pars{{1 \over z^{2} - r_{+}} - {1 \over z^{2} - r_{-}}} \\[3mm] & = {1 \over 2\root{3}} \pars{{1/r_{-} \over 1 - z^{2}/r_{-}} - {1/r_{+} \over 1 - z^{2}/r_{+}}} = {1 \over 2\root{3}} \pars{{r_{+} \over 1 - r_{+}z^{2}} - {r_{-} \over 1 - r_{-}z^{2}}} \\[3mm] & = {1 \over 2\root{3}} \sum_{n = 0}^{\infty}c_{n}z^{2n}\,, \qquad c_{n} \equiv r_{+}^{n + 1} - r_{-}^{n + 1}\,,\quad\verts{z} < r_{-}^{1/2} \end{align}

También, \begin{align} {1 - z^{2} \over z^{4} - 4z^{2} + 1} & = \sum_{n = 0}^{\infty}c_{n}z^{2n} - \sum_{n = 0}^{\infty}c_{n}z^{2n + 2} = \sum_{n = 0}^{\infty}c_{n}z^{2n} - \sum_{n = 1}^{\infty}c_{n - 1}z^{2n} = c_{0} + \sum_{n = 1}^{\infty}\pars{c_{n} - c_{n - 1}}z^{2n} \\[3mm] {z \over z^{4} - 4z^{2} + 1} & = \sum_{n = 0}^{\infty}c_{n}z^{2n + 1} \end{align}

Finalmente, \begin{align} \color{#f00}{\mathrm{f}\pars{n}} & = \color{#f00}{% \left\lbrace\begin{array}{lcl} \ds{{1 \over 2\root{3}}\,c_{0} = 1} & \mbox{if} & \ds{n = 0} \\[1mm] \ds{{1 \over 2\root{3}}\,\pars{c_{n/2} - c_{n/2 - 1}}} & \mbox{if} & \ds{n}\ \mbox{is}\ even \\[1mm] \ds{0} && \mbox{otherwise} \end{array}\right.} \\[3 mm] \color{#f00}{\mathrm{g}\pars{n}} & = \color{#f00}{% \left\lbrace\begin{array}{lcl} \ds{{1 \over 2\root{3}}\,c_{0} = 1} & \mbox{if} & \ds{n = 1} \\[1mm] \ds{{1 \over 2\root{3}}\,\bracks{c_{\pars{n - 1}/2} - c_{\pars{n - 1}/2 - 1}}} & \mbox{if} & \ds{n}\ \mbox{is}\ odd \\[1mm] \ds{0} && \mbox{otherwise} \end{array}\right.} \end{align} $\ds{\color{#f00}{\mbox{where}\ c_{n} = r_{+}^{n + 1} - r_{-}^{n + 1}\,,\quad r_{\pm} = 2 \pm \root{3}}}$.

Answer 4

Uno de los aspectos de la técnica que no es obvio a partir de las otras dos respuestas es simplemente usar uno de recurrencia para eliminar una función de la otra.

Por ejemplo, la segunda repetición da $f(n) = g(n+1) - g(n-1)$ para cada entero $n$, lo que claramente puede ser utilizado (dos veces) para deshacerse de todas las apariciones de $f$ en la primera recurrencia, dejando una sola repetición.