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.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ 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$$. $\endgroup$– Charles MatthewsCommented Sep 25, 2012 at 16:08
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered Sep 25, 2012 at 18:03