# What's the generalized approach for solving non homogenous recurrence relations?

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!

• It is exactly the same story as with the method of undetermined coefficients in ODE. If the right hand side is a polynomial times an exponent, you can find a solution of the same form (possibly, raising the degree a bit). Now just write the general expression, apply the operator, equate the coefficients, and solve the linear system. Commented Nov 2, 2012 at 11:04
• Can you please show me the math, it's just not fitting with the way it's explained in my text book. Thank you. Commented Nov 2, 2012 at 11:18

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