System of linear recurrences

Question

During some computations I came up with the following system of linear recurrences:

$$B_{n+2} = 3B_n + A_n \\ A_n = A_{n-1} + B_{n-1}$$

Here I am trying to find the solution for $B$ (hoping to get some sort of homogeneous equation, find it roots and get the closed form formula).

But I can't solve it. The only thing I can do is $$B_{n+2} = 3B_n + \sum_{i=0}^{n-1} B_i$$, which will not help me to solve recurrence.

So is there a way I can find $B$ without the summation through $n$?

Answer 1

You can transform the above equations into equations only in $A$ and only in $B$: The second equation gives $$ B_n = A_{n+1} - A_n $$ applying this to the first equation gives $$ A_{n+3} - A_{n+2} = 3(A_{n+1} - A_n) + A_n = 3 A_{n+1} - 2 A_n \Rightarrow \\ A_{n+3} = A_{n+2} + 3 A_{n+1} - 2 A_n $$ Similar $$ A_n = B_{n+2} - 3 B_n \\ B_{n+2} - 3 B_n = B_{n+1} - 3 B_{n-1} + B_{n-1} \Rightarrow \\ B_{n+2} = B_{n+1} + 3 B_n - 2 B_{n-1} $$

Answer 2

the equation $$B_{n+2} = 3B_n + \sum_{i=0}^{n-1} B_i$$

is of the form $$B \ast h (n)= 0$$ where $h(n) = \delta(n+2) - 2\delta(n) - \sum_{k=0}^\infty \delta(n)$ is a linear filter. the general way to solve this is similar as the method of using the Laplace transform for solving linear differential equations. the discrete version of the Laplace transform is the the Z-transform :

$$H(z) = \sum_{n= -\infty}^\infty z^{-n} h(n) = z^{-2} - 2 - \frac{1}{1-z} = \frac{z^{-2}-z^{-1}-3+2z}{1-z}$$ $$\frac{1}{H(z)} =\frac{1-z}{1-z-3z^2+2z^3} = \frac{(1-z)}{(2z-1)(z^2-z-1)}$$ perform partial fraction decomposition to get : $$\frac{1}{H(z)} = -\frac{1}{5 (z-1/2)}+\frac{z-3}{5 (-1-z+z^2)} = -\frac{1}{5 (z-1/2)} + \frac{A}{z-\varphi}+\frac{B}{z-\varphi}$$ for some constants $A,B$ and $\varphi = \frac{1+\sqrt{5}}{2}$. the solution is then : $$g(n) = -\frac{1}{10}2^{-n}_{\quad n \ge 1} + A\varphi^{n-1}_{\quad n \ge 1} + B\varphi^{-n+1}_{\quad n \ge 1}$$ with $$g \ast h(n) = \sum_{m=-\infty}^\infty g(m) h(n-m) = \delta(n)$$

i.e. $g(n)$ is the solution of your difference equation for initial condition $B(n) = 0$ for $n < 0$ and $B(0) = 1$, the solution for other initial condition being found by linearity.