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

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
Great! I suppose this only works so nicely for sums and differences, is that correct? – user73041 Apr 21 '13 at 17:15
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

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.