# sequences - recurrence relation [closed]

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.

## closed as too localized by Yemon Choi, Andrés E. Caicedo, Qiaochu Yuan, Andreas Blass, Bugs BunnySep 25 '12 at 20:31

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

• It's actually not hard to find the general solution for the $$z_n$$: there is a particular solution, and then you add the general solution of the homogeneous recurrence. So you should try the same strategy for the $$y_n$$. – Charles Matthews Sep 25 '12 at 16:08

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.
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.