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!

  • $\begingroup$ 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. $\endgroup$ – fedja Nov 2 '12 at 11:04
  • $\begingroup$ Can you please show me the math, it's just not fitting with the way it's explained in my text book. Thank you. $\endgroup$ – SurenNihalani Nov 2 '12 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. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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