1
$\begingroup$

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?

Update:

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$

$\endgroup$
4
  • 2
    $\begingroup$ Can you use GF? $\endgroup$
    – Alex
    Commented May 26, 2015 at 10:48
  • 1
    $\begingroup$ I like finding the generating function $\endgroup$
    – user230734
    Commented May 26, 2015 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
    Commented May 26, 2015 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$ Commented May 26, 2015 at 10:57

3 Answers 3

1
$\begingroup$

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

$\endgroup$
5
  • $\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$ Commented May 26, 2015 at 11:04
  • $\begingroup$ Well IMO roots of the polynomial equation are a bit like 'guessing'. GFs are a systematic approach. $\endgroup$
    – Alex
    Commented May 26, 2015 at 11:16
  • $\begingroup$ @VincentVance: pls see the edit $\endgroup$
    – Alex
    Commented May 26, 2015 at 11:21
  • 1
    $\begingroup$ Thank you, we will begin with general functions soon, so I will certainly keep this method in mind. :) $\endgroup$ Commented May 26, 2015 at 14:41
  • 1
    $\begingroup$ you are welcome $\endgroup$
    – Alex
    Commented May 26, 2015 at 14:49
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you, I think I get it now! $\endgroup$ Commented May 26, 2015 at 14:42
0
$\begingroup$

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).$$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .