How to solve a particular nonhomogeneous recurrence relation

Question

Does anyone know how to solve the particular part in a non-homogeneous recurrence relation?

I know how to solve a homogeneous one, I just can't seem to understand how to find the particular one?

Is there some kind of formula for that?

Here's an example of one:$$a_{n+2}-4a_{n+1}+4a_n=2^n \sin(\frac{\pi n}{3})$$

I know that homogeneous part has two zeros, $x_1$ and $x_2$ which are both $2 $ meaning that the homogeneous part would look like: $$ a_n= (An+B)2^n$$

I don't know how to calculate the non-homogeneous part though. Do you just guess it? If so how? or Is there some kind or a formula/recipe?

thank you for your help!

Answer 1

It is more an art than a science... say your recurrence is $a_{n + 2} + \alpha a_{n + 1} + \beta = f(n)$. The characteristic equation is $x^2 + \alpha x + \beta = 0$, say it has roots $r_1$ and $r_2$. For the homogeneous part, $a_{n + 2} + \alpha a_{n + 1} + \beta = 0$ has solutions of the form $a_n = c_1 r_1^n + c_2 r_2^n$ if $r_1 \ne r2$ and $a_n = (c_1 n + c_2) r_1^n$ when $r_1 = r_2$. Now for the particular solution:

• If $f(n) = c r^n$, and $r \ne r_1$ and $r \ne r_2$, a solution has the form $C r^n$. Substitute to get $C$.
• If $f(n) = c r_1^n$, and $r_1 \ne r_2$, a solution has the form $C n r_1^n$.
• If $f(n) = c r_1^n$, and $r_1 = r_2$, a solution has the form $C n^2 r_1^n$.
• For linear combinations of the above, try linear combinations of the general forms given.

For other forms of $f$, things get hairy...