0

How can I solve the following recurrence equation? Is there a general approach to solve rec. equation with more recursive calls?

$$A(n) = 2A(n-1) + A(n-5)$$

$$A(0) = 1 , A(1) = 2,A(2) = 4, A(3) = 8, A(4) = 16$$

When i try to use methods from more simple equations with just one recursive part, (like repeated substitution) i end up having just chaos and i don't really see how to apply the basecase then. Thanks for taking a look at it.

R-Carver
  • 93

2 Answers2

5

The first step is to solve the equation without taking the initial conditions into account. We do that by assuming that the solution is of the form $A(n) = r^n$. We get $$ A(n) = 2A(n-1) + A(n-5)\\ r^n = 2r^{n-1} + r^{n-5}\\ r^5 = 2r^4 + 1 $$ which has the five solutions $$ r_1 \approx 2.05597\\ r_2 \approx -0.582170-0.526390 i\\ r_3 \approx -0.582170+0.526390 i\\ r_4 \approx 0.554186-0.694593 i\\ r_5 \approx 0.554186+0.694593 i $$ (Yes, four of them are complex. That makes little difference.) The trick now is to recognize that setting the sequence to be any linear combination of these, like so: $$ A(n) = a_1r_1^n + a_2r_2^n + a_3r_3^n + a_4r_4^n + a_5r_5^n $$ also solves the recurrence relation. What is left is to figure out what $a_1, a_2,a_3,a_4, a_5$ should be, and for that, we need the initial conditions. We get the set of equations $$ \cases{A(0) = 1\\A(1) = 2\\A(2) = 4\\A(3) = 8\\A(4) = 16} \implies\cases{a_1 + a_2 + a_3 + a_4 + a_5= 1\\a_1r_1 + a_2r_2 + a_3r_3 + a_4r_4 + a_5r_5= 2\\a_1r_1^2 + a_2r_2^2 + a_3r_3^2 + a_4r_4^2 + a_5r_5^2= 4\\a_1r_1^3 + a_2r_2^3 + a_3r_3^3 + a_4r_4^3 + a_5r_5^3= 8\\a_1r_1^4 + a_2r_2^4 + a_3r_3^4 + a_4r_4^4 + a_5r_5^4= 16} $$ which is not really difficult to solve, although the work load is huge unless you have computers to help you.

Arthur
  • 199,419
0

I tried using Generating Functions, and this is what I've come up with.

$A(n)$ is the coefficient of $x^n$ in $$\frac{1}{1-2x-x^5}$$ Wolfram Alpha gives the power series of the above function as:

$$1 + 2 x + 4 x^2 + 8 x^3 + 16 x^4 + 33 x^5 + 68 x^6 + 140 x^7 + 288 x^8 + 592 x^9 + 1217 x^{10} + \dots $$

So the first few terms are: $A(1)=2$, $A(2)=4$, $A(3)=8$, $A(4)=16$, $A(5)=33$, $A(6)=68$, $A(7)=140$, $A(8)=288$ and so on.

Note: The method is not so satisfactory since all you get in the end is a power series and no closed form. That's why I didn't show the method.

Aritra Das
  • 3,528
  • How would you go about encoding the initial conditions into the generating function? – Arthur Nov 20 '15 at 18:38
  • @Arthur Well, the generating function in general takes the form $f(x) = c_0 +c_1x +c_2x^2 + \dots = \sum_{i=0}^{\infty} c_i x^i$, where $A(n)$ is the coefficient of $x^n$ in this function, that is, $A(n) = c_n$. Because $A(0), A(1), A(2), \dots$ are given, we have $c_0 = 1, c_1 = 2, c_2 = 4, \dots c_4 = 16$ – Aritra Das Nov 20 '15 at 18:45
  • So the fact that the denominator is a reverse of the characteristic polynomial is a coincidence? – Arthur Nov 20 '15 at 18:53
  • @Arthur Not really. The initial conditions are nice in the sense that they mostly satisfy the recurrence if all $A(i)$ with $i<0$ are assumed to be $0$. So all that remains while calculating the generating function is $1$ on the right hand side, and a polynomial on the left.

    While in your approach, to go from $A(n)$ to $A(n-1)$ you have to divide by $r$ (from $r^5$ to $r^4$), I have to multiply be $x$ so as to shift the coefficients of the generating function one place to the right. If your characteristic polynomial were to be $2x^2-x-1$ my generating function would be $\frac{1}{-x^2-x+2}$.

     – Aritra Das Nov 20 '15 at 19:16