# Rules Regarding Particular Solutions for Recurrence Relations

Suppose I have the recurrence relation

$a_n = - a_{n-1} + a_{n-2} + 2^n + n$

Is it alright to solve for the homogeneous 'general' solution and then split the solving of the particular solution into two cases (one for $2^n$ and one for $n$) then combine them for the final result?

-
That is not a recurrence relation. There should be an $=$ somewhere in there. – Cameron Buie Apr 21 '13 at 16:46
@CameronBuie Sorry, suppose that it is rearranged so that $a_n$ is the only term on the LHS – user73041 Apr 21 '13 at 16:54

Indeed, that's just fine. Let's suppose that you've found a particular solution $b_n$ for $$b_n=-b_{n-1}+b_{n-2}+2^n$$ and a particular solution $c_n$ for $$c_n=-c_{n-1}+c_{n-2}+n.$$ Putting $a_n=b_n+c_n$ for all $n$, we have \begin{align}a_n &= b_n+c_n\\ &= (-b_{n-1}+b_{n-2}+2^n)+(-c_{n-1}+c_{n-2}+n)\\ &= -(b_{n-1}+c_{n-1})+(b_{n-2}+c_{n-2})+2^n+n\\ &= -a_{n-1}+a_{n-2}+2^n+n,\end{align} as desired. All you have to do is add the general homogeneous solution to the particular solution $a_n$ and you're done.
Scalar multiples are okay, too. For example, if you'd had $3n$ in the recurrence instead of $n,$ we could still find $b_n,c_n$ as above, and then set $a_n=b_n+3c_n$ instead. You're right though, that in general we can only "split things up" this way over sums, differences, and scalar multiples. – Cameron Buie Apr 21 '13 at 17:18