# How to find explicit formula for two recursions?

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!

• I like the intuition that they're "intertwining"! – goblin Jun 14 '16 at 6:41
• Is this a linear algebra class, or something else? What techniques have you learned? – Mehrdad Jun 14 '16 at 10:54
• I would suggest as a first step also if you're stuck to try writing out the first few terms of each sequence... – danimal Jun 14 '16 at 12:00

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.

• Nice solution! I enjoyed it. – Majid Jun 13 '16 at 14:37
• Thanks! I am, of course, leaving quite a bit of legwork to the reader; namely, what is $A^n$, and how precisely does one extract $f(n),g(n)$ from it. The latter is straightforward; for the former, I think one ends up with $A^n =\begin{pmatrix} P_n(B) & P_{n-1}(B) \\ P_{n-1}(B) & P_{n-2}(B) \end{pmatrix}$ where $P_n(B)$ is a sequence of polynomials in the 2-by-2 submatrix $B$ sitting in the upper-left corner of $A$. @majid – Semiclassical Jun 13 '16 at 14:40
• Actually, I was first thinking of finding two separate recursive sequences for $f(n)$ and $g(n)$, and then one can obtain the solutions by the known techniques to do so, but when I saw your answer, I gave up to write down my answer because in my point of view yours is nicer! – Majid Jun 13 '16 at 14:44
• The 4 eigenvalues of $A$ are $\pm \sqrt{2 \pm \sqrt{3}}$ – DanielV Jun 13 '16 at 15:05
• And consequently, $A=MDM^{-1}$, where (using $r:=\sqrt{2+\sqrt{3}},s:=\sqrt{2-\sqrt{3}}$) $D=\begin{pmatrix}r&0&0&0\\0&s&0&0\\0&0&-r&0\\0&0&0&-s\end{pmatrix}$ and $M=\begin{pmatrix}1+\sqrt{3}&1-\sqrt{3}&1+\sqrt{3}&1-\sqrt{3}\\r&s&-r&-s\\r-s&s-r&s-r&r-s\\1&1&1&1\end{pmatrix}$ – Klaus Draeger Jun 14 '16 at 12:33

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

• This is elementary, but in no way is a "technique commonly used" for this kind of problem. – Ryan Reich Jun 14 '16 at 10:12
• @RyanReich: I don't know how common it is. It reduces the problem from coupled recurrences to a single one, which OP may know how to handle. Semiclassical's matrix approach is also a good one. I think having more tools in one's box is an advantage, so I showed this one. – Ross Millikan Jun 14 '16 at 13:45
• @YvesDaoust Ross' technique is clearly just finding an eigenvector of the linear system. The difference is that using linear algebra constitutes an actual technique, and the computation above is just ad-hoc. The idea behind it may be the same in both cases, but the general principle is obscured here. This computation is not generalizable, which is why I can't call it a technique. – Ryan Reich Jun 14 '16 at 17:04
• @YvesDaoust Elimination is a goal, not a technique. Gauss-Jordan elimination is a technique. Random substituting in the hopes of achieving a separated system is ad-hoc. The nonlinear case is not relevant here since the question asked for similar problems; if, however, you can demonstrate a generalizable technique that applies to both linear and nonlinear equations, that would be a great answer. – Ryan Reich Jun 15 '16 at 3:16


$\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}}}$.

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.