2
$\begingroup$

I am trying to understand how do you solve non homogenous recurrence relations.

So , for example, consider the following equation, $(A-2)^2(A-1)g = 3(n^2)(2^n) + (2^n)$ So , $A$ being the advancement operator. In general , $A$ just takes the value and use recurrence to get you to the next value in the series. $g$ being the function to be found.

What's the generalized approach to solve these kind of problems ? Googling around upto first ten results tell you the solution but not do a good job of tell the algorithm to solve this .

Thank you!

  • 0
    Can you please show me the math, it's just not fitting with the way it's explained in my text book. Thank you.2012-11-02

1 Answers 1

1

Rewrite this as $(1-2A^{-1})^2(1-A^{-1})x=y$ for $x=(x_n)_{n\geqslant0}$ and some $y=(y_n)_{n\geqslant0}$ and invert the operator $(1-2A^{-1})^2(1-A^{-1})$. Note that $ B=[(1-2A^{-1})^2(1-A^{-1})]^{-1}=\sum_{i\geqslant0}(i+1)2^iA^{-i}\cdot\sum_{j\geqslant0}A^j=\sum_{k\geqslant0}b_kA^{-k}, $ for some coefficients $(b_k)_{k\geqslant0}$, which happen to be $ b_k=\sum_{i=0}^k(i+1)2^i=k2^{k+1}+1. $ All this leads to $ x_n=\sum_{k=0}^nb_ky_{n-k}. $ In the case at hand, $x_n=g_{n}$ for every $n\geqslant3$ and $y_{n+3}=z_{n}$ with $z_n=(3n^2+1)2^n$ for every $n\geqslant0$. The triplet $(y_0,y_1,y_2)$ corresponds to the initial conditions $(g_0,g_1,g_2)$ through the system $ y_0=g_0,\quad y_1=g_1-5g_0,\quad y_2=g_2-5g_1+8g_0. $ Finally, introducing $b_{-1}=b_{-2}=0$, one gets, for every $n\geqslant0$, $ g_n=\sum_{k=0}^{n-3}b_kz_{n-3-k}+b_{n-2}(g_2-5g_1+8g_0)+b_{n-1}(g_1-5g_0)+b_ng_0. $