particular solution of recurrence relation help

Question

I'm having a hard time understanding how to find the particular solution for a recurrence relation. I have a particular part of the relation as (2n + 3 +4*3^n). I have already determined the homogenous equation, so for this, do I need to break the particular solution into two parts, F1=2n+3 and F2=4*3^n ? I saw examples that I thought mirrored what I need to do that did this, but then got confused. I have to write the particular solution to this recurrence relation, and a general solution to the recurrence relation, which I assume will just be the general solution I already found with the associated homogenous rr and what I find for the particular solution. Can anyone help?

Answer 1

In most textbooks this is not well-explained, simply because it is a hassle to write this all out in a general manner.

To answer your question directly; yes, split the particular solution in two parts, solve them independently and then add the two solutions.

Here's why. Since you don't provide the recurrence relation itself (and it's not important for your question) I'll pretend your recurrence relation is $$y_n-3y_{n-1}=2n+3+4\cdot 3^n.$$

Suppose you find:

• A solution $h_n$ for the homogeneous recurrence relation $y_n-3y_{n-1}=0$

• A solution $f_n$ for the recurrence relation $y_n-3y_{n-1}=2n+3$

• A solution $g_n$ for the recurrence relation $y_n-3y_{n-1}=4\cdot 3^n$

Then define $y_n=h_n+f_n+g_n$ and observe that $$y_n-3y_{n-1} = h_n+f_n+g_n -3h_{n-1} -3f_{n-1}-3g_{n-1},$$ which after reordering becomes $$(h_n-3h_{n-1})+(f_n-3f){n-1})+(g_n-3g_{n-1})=0 + 2n+3+ 4\cdot 3^n,$$ which means that $y_n$ is a solution for your complete non-homogeneous recurrence relation.

If you understand the above, note that the only thing that we used from the specific equation that I took was that it is linear; the same 'trick' works for any other linear recurrence relation and hence (I assume) also for yours.