Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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. – fedja Nov 2 '12 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. – snihalani Nov 2 '12 at 11:18
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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