Question

I have to find the expression of $(y_n)$ defined by :

$$y_{n+1}=a y_n+b z_n+c$$

where $(z_n)$ is an arithmetico-geometric sequence :

$$z_{n+1}=d z_n+e$$

and $a,b,c,d,e$ real numbers.

Thank you for your help.

Answer 1

Note that the vector $X_n = \pmatrix{y_n\cr z_n\cr}$ satisfies the recurrence $X_{n+1} = A X_n + C$ where $$ A = \pmatrix{a & b\cr 0 & d\cr},\ C = \pmatrix{c\cr e\cr} $$ and thus $$ X_n = A^n C X_0 + (A - I)^{-1} (A^n - I) C $$ Moreover, $$ A^n = \pmatrix{ a^n & b (a^n - d^n)/(a-d)\cr 0 & d^n\cr}$$ This is all assuming $1,a,d$ are distinct. The other cases may be obtained as limits.

Answer 2

One standard way to solve recurrence relations is with generating functions. In this case, let $f$ and $g$ be the ordinary generating functions of the sequences $y$ and $z$. Then the generating function equivalent of your recurrence relations would be $$\frac{g(x)-g(0)}x=d\cdot g(x)+\frac e{1-x}$$ and $$\frac{f(x)-f(0)}x=a\cdot f(x)+b\cdot g(x)+\frac c{1-x}.$$ You can then solve these relations for the generating functions $$g(x)=\left(\frac{e\cdot x}{1-x}+g(0)\right)\cdot \frac 1{1-xd}$$and $$f(x)=\left(x\cdot b\cdot g(x)+\frac{x\cdot c}{1-x}+f(0)\right)\frac 1{1-ax}.$$ Lastly, you need to find the partial fraction decomposition of $f$. Using geometric series and its derivatives, you can then read off the coefficients of the partial fraction decomposition to get an explicit solution for the terms in your sequences.

There are lots of examples along these lines in Wilf's book Generatingfunctionology, chapter 2 sections 1-2.