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!

$\endgroup$
2
  • $\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
    Commented Nov 2, 2012 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$ Commented Nov 2, 2012 at 11:18

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .