Warning: This node uses a fair bit of HTML mathematical entities. It may not render correctly in your browser; it's been checked in Mozilla 1.0 and 1.1.
The most general form of such a beast is
Fn = an-1Fn-1 + an-2Fn-2 + ...
To
solve a relation of this form, we identify each F
n with x
n to form a
polynomial
xn = an-1xn-1 + an-2xn-2 + ...
Now if we let
d be the largest integer such that
an-d ≠ 0, then we can divide the whole equation through by
xn-d to reduce it down to a simpler form.
Next, we need to find the roots of a polynomial). This will give us a set of d roots:
{ r0, ..., rd-1 }
From here, it gets very messy, so we will only look at the case
d = 2.
Wondering why this method works? The explanation is quite convoluted, involving generating functions and "intelligent guessing", so we won't go into it here. It should be covered in an elementary undergraduate-level textbook on discrete mathematics.
Depending on the nature of the roots r0, r1, there are 2 cases to consider.
Case 1: r0 ≠ r1
In this case, the form of the
solution will be
Fn = Ar0n + Br1n
A, B are
constants that depend on the initial values of
Fn.
Case 2: r0 = r1
In this case, the form of the
solution will be
Fn = Ar0n + Bnr0n
(
Note the 'n' in the second term!).
A, B are
constants that depend on the initial values of
Fn.
The insightful reader may note that we might get complex roots. This is not a problem; we just use Case 1, and get an answer that involves sine and cosine terms.
A worked example:
Fn = Fn-1 + 2Fn-2
First, we get the expression
xn = xn-1 + 2xn-2
which is equivalent to
x2 = x + 2
The roots of this (given by the
quadratic formula) are
x = 2 and x = -1
Therefore, using Case 1, the form of the solution is
Fn = A(2)n + B(-1)n
Now, imagine our initial conditions are
F0 = 1 and F1 = 1
We get the two
simultaneous equations
1 = A + B and 1 = 2A - B
Solving these using standard high-school techniques, we get
A = 2/3 and B = 1/3
Finally, our complete closed-form
solution is
Fn = (2/3)2n + (2/3)(-1)n