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.
On
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.
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.