How to find explicit formula for two recursions?

Question

I have to find explicit solution for two intertwining recursions

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

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

What techniques are commonly used for this types of problem? Thanks!

Answer 1

Hint: We can write this recurrence in matrix form as $$\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}$$ or more succinctly as $\Phi(n)=A\Phi(n-1)$. From this we observe that $\Phi(n)=A^n \Phi(0)$ where $\Phi(0)=(0,1,1,0)^T$. Hence this has been converted to a problem of linear algebra.

Answer 2

You can write $$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)$$ And you have a single recurrence

Answer 3

One obvious technique that isn't obvious from the other two answers is to simply use one recurrence to eliminate one function from the other.

For example, the second recurrence gives $f(n) = g(n+1) - g(n-1)$ for every integer $n$, which can clearly be used (twice) to get rid of all occurrences of $f$ in the first recurrence, leaving a single recurrence.

Answer 4

$\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}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{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}{\partial #3^{#1}}} \newcommand{\root}[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{% \left.\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{and}\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.}$

---

With $\ds{\mathbf{u}\pars{n} \equiv {\mathrm{f}\pars{n} \choose \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. \\[3mm] & = \bracks{% {3 \over 2}\pars{\begin{array}{cc}\ds{0} & \ds{1}\\ \ds{1} & \ds{0} \end{array}} + \half\,\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} where $\ds{\vec{a} \equiv {3 \over 2}\,\hat{x} + \half\,\ic\,\hat{y}}$ and $\ds{\braces{\sigma_{i}\ \mid\ i = 0,x,y,z}}$ are the Pauli Matrices. Then, \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} which leads to $$ \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} $$ Multiply both sides, by the left, with the matrix $\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}

The zeros of $\ds{w^{2} - 4w + 1 = 0}$ are given by $\ds{r_{\pm} = 2 \pm \root{3}}$ with $\ds{r_{-} \approx 0.2679}$ and $\ds{r_{+} = 1/r_{-} \approx 3.7321}$ such that \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}

Also, \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}

Finally, \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.} \\[3mm] \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}}}$.