getting wrong solution to system of recurrences

Question

i have been stuck on this question for hours now and would really appreciate any help. So i have the following system of recurrences $$a_n=1+a_{n-1}, b_n = 1+b_{n-1}+2a_{n-1}, a_1=b_1=1, n\geq 2.$$ When i enter it into maple i get $$a_n=n,b_n=n^2$$ however when i try solving it using generator functions i keep getting $$a_n=n-1,b_n=(n+1)^2.$$ I would really appreciate if anyone could find where i am going wrong. My solution is below.

let $$A(Z)=\sum_{n\geq 0}a_nz^n, B(Z)=\sum_{n\geq 0}b_nz^n.$$ Then we would have $$\sum_{n \geq 1}a_nz^n = A(z)-1= \frac{1}{1-z}-1+zA(z).$$ i.e, $$A(z)-1=\frac{1}{1-z}-1+zA(z).$$ doing something similar for the other recurrence i got $$B(z)-1 = \frac{1}{1-z}-1+zB(z)+2zA(z).$$ solving these two systems of linear equations i finally got $$A(z)= \frac{1}{z^{2}-2 z+1},B = -\frac{z+1}{z^{3}-3 z^{2}+3 z-1}.$$ After this, i ask maple to give me A(z) in powerseries form and i get the following: $$A(z)=\sum_{n\geq 0}(n+1)z^n.$$ Matching coefficients with $$A(z) = \sum_{n \geq 0}a_nz^n$$ i finally get the wrong answer: $$a_n = n+1.$$ If anyone could find where i went wrong, i would really appreciate it.

Answer 1

Typically a matrix form will provide an enlightenment:

$$ \begin{Bmatrix} a_{n} \\ b_{n} \end{Bmatrix} = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix} \begin{Bmatrix} a_{n-1} \\ b_{n-1} \end{Bmatrix} + \begin{Bmatrix} 1 \\ 1 \end{Bmatrix} $$

From which, through repeated substitution, we can deduce that

$$ \begin{Bmatrix} a_{n} \\ b_{n} \end{Bmatrix} = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}^{n-1} \begin{Bmatrix} a_{1} \\ b_{1} \end{Bmatrix} + \sum_{m=0}^{n-2} \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}^{m} \begin{Bmatrix} 1 \\ 1 \end{Bmatrix} $$

The square matrix has a very interesting property:

$$ \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}^{m} = \begin{bmatrix} 1 & 0 \\ 2m & 1 \end{bmatrix} $$

Therefore, the second equation becomes

$$ \begin{Bmatrix} a_{n} \\ b_{n} \end{Bmatrix} = \begin{bmatrix} 1 & 0 \\ 2n-2 & 1 \end{bmatrix} \begin{Bmatrix} a_{1} \\ b_{1} \end{Bmatrix} + \sum_{m=0}^{n-2} \begin{bmatrix} 1 & 0 \\ 2m & 1 \end{bmatrix} \begin{Bmatrix} 1 \\ 1 \end{Bmatrix} $$

Substituting $a_{1}=b_{1}=1$ we get the following:

$$ \begin{aligned} a_{n}&=n \\ b_{n}&=n^{2} \end{aligned} $$

Answer 2

The desired solutions can be developed very quickly by induction. Thus,

$$ \begin{align} &a(1)=1\\ &a(2)=a(1)+1=2\\ &a(3)=a(2)+1=3\\ &\vdots\\ &a(n)=a(n-1)+1=n \end{align} $$

and

$$ \begin{align} &b(1)=1\\ &b(2)=b(1)+1+2a(1)=4\\ &b(3)=b(2)+1+2a(2)=9\\ &b(4)=b(3)+1+2a(3)=16\\ &\vdots\\ &b(n)=b(n-1)+1+2a(n-1)=n^2 \end{align} $$