4

I have a problem in solving this equation :

$x_{n+2} + 3\ x_{n+1} + 2\ x_{n} = 5 \times 3^n $

given that $x_{0} = 0$ and $x_{1} = 1$.

I solved the homogeneous associated equation and got $v_{n} = c_{1} \times (-1)^{n} + c_{2} \times (-2)^{n}$ (where $c_{1}$ and $c_{2}$ are constants). Could somebody explain the general method for solving second order non-homogeneous linear recurrence ?

jdw
  • 49
  • Why is the function's name $x$? Also, what have you tried? Have you tried to input some values and see the results? Solving similar equations? If so, please add it to the question. – JMCF125 Dec 28 '13 at 21:25
  • just changed the question and add info. – jdw Dec 28 '13 at 21:46
  • +1, exactly! Sorry I don't know how to answer. But now it's more likely you get an answer. – JMCF125 Dec 28 '13 at 21:48
  • 2
    The 'annihilator' method will give you this question quite easily. Have a look around the Internet. (There's a similar method for DE, so include recurrence in your search to avoid confusion). – G. H. Faust Dec 28 '13 at 21:56

3 Answers3

2

Well, you need to find a particular solution of the inhomogeneous equation, and the rhs suggest that something of the form $c(n)3^n$ should work. The simplest form of $c$ is a constant, so try that. If it works, you are golden, if not, try a linear function, etc, then add the homogeneous solution and you are good.

Igor Rivin
  • 25,994
  • 1
  • 19
  • 40
1

I have just found the solution. This is not general method, but some piece of heuristics. May be it somehow will help you to find some solutions in simple cases. I use method of undetermined coeficients. I guess, that should be $$x_n=c3^n+d(-1)^n,$$ for some real constants $c,d$. Now, calculation of $c,d$ is very simple. We have also $$x_{n+1}=3c3^n-d(-1)^n$$ $$x_{n+2}=9c3^n+d(-1)^n,$$ so: $$x_{n+2}+3x_{n+1}+2x_n=9c3^n+d(-1)^n+ 9c3^n-3d(-1)^n+2c3^n+2d(-1)^n=20c3^{n}$$ From the recurrence must be: $$20c3^{n}=5.3^n,$$ so: $c=\frac{1}{4}$. Now we know, that $$\frac{3^n}{4}+d(-1)^n$$ satisfies your recurrence. And because $x_0=0$, we must have $d=-\frac14$. Therefore we have following result: $$x_n=\frac{3^n}{4}-\frac{(-1)^n}4.$$

Marek
  • 695
  • 3
  • 14
  • 1
    How can you 'guess' that the $ c_{2} (-2)^{n}$ isn't part of the general solution? I have the same answer but I first need to resolve some equations before knowing that $c_{2} = 0$. – jdw Dec 29 '13 at 08:02
  • It's just my heuristic. First I was trying shapes $P(n).3^n$, where $P(n)$ is polynomial. Because in that case all terms $x_n,x_{n+1},x_{n+2}$ are something times $3^n$, so there is a chance get in result your recurrence. First try didn't work. But later I was trying shapes $P(n).3^n+Q(n)(-1)^n$ and I was successful. But, you can also transform your recurrence to a linear with constants. But I forgot details of standard procedure, how to solve that kind of recurences. – Marek Dec 30 '13 at 23:17
0

Use generating functions directly. Define $G(z) = \sum_{n \ge 0} x_n z^n$, multiply by $z^n$ and sum over $n \ge 0$, recognize a few sums: $$ \frac{G(z) - x_0 - x_1 z}{z^2} + 3 \frac{G(z) - x_0}{z} + 2 G(z) = 5 \frac{1}{1 - 3 z} $$ As partial fractions: $$ A(z) = \frac{1}{4} \cdot \frac{1}{1 - 3 z} - \frac{1}{4} \cdot \frac{1}{1 + z} $$ Everything in sight is just geometric series; $$ a_n = \frac{3^n - (-1)^n}{4} $$

vonbrand
  • 27,812