1

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?

user73041
  • 435
  • 1
  • 5
  • 17

1 Answers1

1

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.

Cameron Buie
  • 102,994
  • 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