Solve a system of reccurence equations

Question

$a_{n+1}=2a_n-b_n$

$b_{n+1}=a_n+4b_n$

$a_0=2,b_0=1$

Using generating functions,

$$\sum_{n=0}^{\infty}a_{n}x^{n}-a_0=2x\sum_{n=0}^{\infty}a_nx^n-x\sum_{n=0}^{\infty}b_nx^n$$

$$\sum_{n=0}^{\infty}b_{n}x^{n}-b_0=x\sum_{n=0}^{\infty}a_nx^n+4x\sum_{n=0}^{\infty}b_nx^n$$

$$f(x)=\sum_{n=0}^{\infty}a_{n}x^{n},g(x)=\sum_{n=0}^{\infty}b_{n}x^{n}$$

Now we get

$$f(x)(1-2x)+xg(x)=2$$

$$xf(x)-4xg(x)=1$$

From this we get

$$f(x)=\frac{9}{4-7x}=\frac{9}{4}\cdot\frac{1}{1-\frac{7}{4}x}=\frac{9}{4}\cdot\sum_{n=0}^{\infty}\left(\frac{7}{4}\right)^nx^n$$

But this is not correct since $a_0=2$ and we got that $a_n=\frac{9}{4}\cdot\left(\frac{7}{4}\right)^n$.

Then, for $g(x)$ we get

$$g(x)=\frac{5+7x}{4x(4-7x)}=\frac{5+7x}{x(16-28x)}=\frac{A}{x}+\frac{B}{16-28x}$$

Here is another problem, finding (if exists), the power series of $1/x$.

How solve this system?

Answer 1

Here is my solution to get the generating functions.

I have shown every step so any errors can be readily found.

The method should be valid even if there are errors.

Let $A(x) =\sum_{n=0}^{\infty} a_n x^n $ and $B(x) =\sum_{n=0}^{\infty} b_n x^n $.

Then $A(x)-a_0 =\sum_{n=1}^{\infty} a_n x^n =x\sum_{n=0}^{\infty} a_{n+1} x^n $ so $(A(x)-a_0)/x =\sum_{n=0}^{\infty} a_{n+1} x^n $.

Similarly, $(B(x)-a_0)/x =\sum_{n=0}^{\infty} b_{n+1} x^n $.

Therefore, from the recurrances,

$(A(x)-a_0)/x =2A(x)-B(x) $ and $(B(x)-b_0)/x =A(x)+4B(x) $.

From the first, $A(x)-a_0 =2xA(x)-xB(x) $ or $B(x) =(A(x)(1-2x)-a_0)/(2x) $.

From the second, $A(x) =(B(x)(1-4x)-b_0)/x $.

Therefore

$\begin{array}\\ A(x) &=(B(x)(1-4x)-b_0)/x\\ &=(((A(x)(1-2x)-a_0)/(2x))(1-4x)-b_0)/x\\ \text{or}\\ xA(x) &=((A(x)(1-2x)-a_0)/(2x))(1-4x)-b_0\\ &=(A(x)(1-2x)(1-4x)-a_0(1-4x))/(2x))-b_0\\ \text{or}\\ (xA(x)+b_0)(2x) &=A(x)(1-2x)(1-4x)-a_0(1-4x)\\ \text{or}\\ 2x^2A(x)+2xb_0 &=A(x)(1-2x)(1-4x)-a_0(1-4x)\\ \text{or}\\ (2x^2-(1-2x)(1-4x))A(x) &=-a_0(1-4x)-2xb_0\\ \text{or}\\ (2x^2-(1-6x+8x^2))A(x) &=-a_0+x(4a_0-2b_0)\\ \text{or}\\ (-6x^2-1+6x)A(x) &=-a_0+x(4a_0-2b_0)\\ \text{or}\\ (6x^2-6x+1)A(x) &=a_0+x(-4a_0+2b_0)\\ \end{array} $

Putting in the initial values, $(6x^2-6x+1)A(x) =a_0+x(-4a_0+2b_0) =2-6x $ so that $A(x) =\dfrac{2-6x}{6x^2-6x+1} $.

$B(x)$ can then be gotten, but I'll stop here.

Answer 2

Hint:  written in matrix form:

$$ \begin{pmatrix} a_{n+1} \\ b_{n+1} \end{pmatrix} = \begin{pmatrix} 2 & -1 \\ 1 & 4 \end{pmatrix} \begin{pmatrix} a_{n} \\ b_{n} \end{pmatrix} $$

Let $A_n = \begin{pmatrix} a_{n+1} \\ b_{n+1} \end{pmatrix} \,$, $A = \begin{pmatrix} 2 & -1 \\ 1 & 4 \end{pmatrix}\,$ then $A_n = A^n \, A_0\,$ so the problem reduces to calculating $A^n$.

The Jordan normal form $A=P\,J\,P^{-1}$ where $P$ is invertible and $J$ is upper triangular gives:

$$ P = \begin{pmatrix} -1 & 1 \\ 1 & 0 \end{pmatrix}\,, \quad J = \begin{pmatrix} 3 & 1 \\ 0 & 3 \end{pmatrix}\,, \quad P^{-1} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} $$

Since $A^n = P\,J^n\,P^{-1}\,$ the last step is to calculate $J^n\,$. Let:

$$J = \begin{pmatrix} 3 & 1 \\ 0 & 3 \end{pmatrix} = \begin{pmatrix} 3 & 0 \\ 0 & 3 \end{pmatrix} + \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} = J_0 + J_1 $$

Note that $J_0, J_1$ commute, and $J_1^2 = O\,$ (the zero matrix) so:

$$ \require{cancel} J^n = (J_0+J_1)^n = J_0^n + \binom{n}{1} J_0^{n-1} J_1 + \cancel{\binom{n}{2} J_0^{n-2} J_1^2 + \cdots} = J_0^n + n J_0^{n-1} J_1 $$

Finally, putting everything back together:

$$ A_n = P\,\left(J_0^n + n J_0^{n-1} J_1\right)\,P^{-1}\,A_0 \quad\quad \left( \text{where of course} \;\; J_0^n = \begin{pmatrix} 3^n & 0 \\ 0 & 3^n \end{pmatrix}\,\right) $$