Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

closed as too localized by Yemon Choi, Andres Caicedo, Qiaochu Yuan, Andreas Blass, Bugs Bunny Sep 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

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.