I have a question about how to find the particular solutions when trying to solve recurrence relations. For example, trying to solve

$$ a_{n+2} = -4a_n + 8n2^n $$

I begin with finding the roots in the characteristic polynomial associated with the homogeneous equation, so

$ r_1 = 2i $ and $r_2 = -2i. $

Then, because the roots are complex, the general solution is

$$ a_n^{(h)} = 2n\left(\alpha \cos\left(\frac{πn}{2}\right)+\beta \sin\left(\frac{πn}{2}\right)\right) $$

Now, my textbook suggests trying a function of the form

$$ (An+B)2^n $$

when trying to find the particular solution. I don't understand why and I have come across a couple of other examples which have made me equally confused as I am this time. Could anyone shed some light on the matter? Is there some sort of "abc-solution" for this?


Here is what the book tells me to do. Only I don't really understand how to use it in this example.

The book tells me this:

For the case of the nonhomogeneous second-order relation

$ a_n + C_1a_{n-1} + C_2a_{n-2} = kr^n $

where k is a constant, we find that

a) $ a_n^{(p)} = Ar^n $ for A a constant, if $r^n$ is not a solution of the associated homogeneous relation.

b)$ a_n^{(p)} = Bnr^n$ where B is a constant, if the general solution = $c_1r^n + c_2r_1^n$ where $r_1 \neq r$

c) $a_n^{(p)} = Cn^2r^2$ for C a constant, when the general solution = $(c_1 + c_2n)r^n$

  • 2
    $\begingroup$ Can you use GF? $\endgroup$ – Alex May 26 '15 at 10:48
  • 1
    $\begingroup$ I like finding the generating function $\endgroup$ – user230734 May 26 '15 at 10:48
  • $\begingroup$ Can you write down the general method you are working with? Or give a link? I never heard of this method, I would like to find out how to solve recurrences using this. Thanks. $\endgroup$ – user230734 May 26 '15 at 10:51
  • $\begingroup$ And here I thought this was how everyone solved them. Not sure I can give a link since it's in my book but basically you begin finding the roots to the characteristic polynomial and formulate the general solution, then I guess it is some kind of guessing game to find the particular solution but there are methods to make qualified guesses, I just don't understand them. Then you add the general and the particular solution. Not sure if I answered your question. $\endgroup$ – VincentVance May 26 '15 at 10:57

To use GF you need to multiply both sides by $z^k$ for some variable $|z|<1$ and sum over k. A generating function is a function of the type $G(z) = \sum_{k=0}^{\infty} a_k z^k$, so the first term on RHS will be $-4 G(z)$ and so on.

Algebraically you need to get $G(z)$ on LHS and some function $\Phi(z)$ on RHS and equate coefficients of $z^n$. This will be your 'closed-form expression' for $a_n$.

EDIT: here's the equation. You `massage' LHS a bit to get $\frac{G(z) -a_0 -a_1 z}{z^2}$ and set $2z=s$ and $ S=\sum_{k=0}^{\infty} ks^k $ to get $$ G(z) -a_0 -a_1 z = -4 z^2 G(z) +8 z^2 S $$

now you need to follow my suggestions above to get what you need

  • $\begingroup$ Thank you for your answer. If you could see my face now you would probaby laugh because I am so confused. We haven't been using generating functions for this, so that would be a whole new thing. I will edit my original post to share what the book says, and hopefully someone smarter than me can translate in into dumb-people-language for me. $\endgroup$ – VincentVance May 26 '15 at 11:04
  • $\begingroup$ Well IMO roots of the polynomial equation are a bit like 'guessing'. GFs are a systematic approach. $\endgroup$ – Alex May 26 '15 at 11:16
  • $\begingroup$ @VincentVance: pls see the edit $\endgroup$ – Alex May 26 '15 at 11:21
  • 1
    $\begingroup$ Thank you, we will begin with general functions soon, so I will certainly keep this method in mind. :) $\endgroup$ – VincentVance May 26 '15 at 14:41
  • 1
    $\begingroup$ you are welcome $\endgroup$ – Alex May 26 '15 at 14:49

The short version is that if your right hand side is a product of a polynomial in $n$ of degree $k$ and an exponential, your first guess for a particular solution will be a product of a polynomial in $n$ of degree $k$ and an exponential with the same base. This may fail if the form you have assumed is annihilated by the recurrence operator; for instance, this will not work for solving $a_{n+1}=2a_n+2^n$. If this happens, you try raising the degree of the polynomial. So in my example you would assume a particular solution of $(An+B)2^n$.

This form has a chance from the start because if you take a linear recurrence with constant coefficients and substitute in a product of a polynomial and an exponential, you get a product of a polynomial and an exponential. So you at least get the right form in this situation. When you look a little more carefully, you find that except when the recurrence operator sends your form to zero, this approach really does work. Raising the degree "adds independent variables" enough to eventually get you away from the functions which your recurrence operator sends to zero.

  • $\begingroup$ Thank you, I think I get it now! $\endgroup$ – VincentVance May 26 '15 at 14:42

when i need to find a particular solution of $$a_{n+2} = -4a_n + 8n2^n $$ find it easier to make a change of variable $$u_n = a_n 2^{-n}, a_n = 2^n u_n.$$ the recurrence relation for $u_n$ is simpler and is $$2^{n+2}u_{n+2}=-4\, 2^nu_n+8n2^n\to u_{n+2}=-u_n+2n.\tag 1$$ for $(1),$ i can try $$u_n = an + b \to a(n+ 2)+b=-an - b+2n $$ gives $$a = 1, b = -1, u_n = n - 1, a_n = 2^n(n-1).$$

  • 1
    $\begingroup$ @VincentVance, you are welcome. $\endgroup$ – abel May 26 '15 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.