*
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

F_{n} = a_{n-1}F_{n-1} + a_{n-2}F_{n-2} + ...

To

solve a relation of this form, we identify each F

_{n} with x

^{n} to form a

polynomial
x^{n} = a_{n-1}x^{n-1} + a_{n-2}x^{n-2} + ...

Now if we let

`d` be the largest integer such that

`a`_{n-d} ≠ 0, then we can divide the whole equation through by

`x`^{n-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:

{ r_{0}, ..., r_{d-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 `r`_{0}, r_{1}, there are 2 cases to consider.

#### Case 1: `r`_{0} ≠ r_{1}

In this case, the form of the

solution will be

F_{n} = Ar_{0}^{n} + Br_{1}^{n}

`A, B` are

constants that depend on the initial values of

`F`_{n}.

#### Case 2: `r`_{0} = r_{1}

In this case, the form of the

solution will be

F_{n} = Ar_{0}^{n} + Bnr_{0}^{n}

(

*Note the 'n' in the second term!*).

`A, B` are

constants that depend on the initial values of

`F`_{n}.

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:

F_{n} = F_{n-1} + 2F_{n-2}

First, we get the expression

x^{n} = x^{n-1} + 2x^{n-2}

which is equivalent to

x^{2} = 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

F_{n} = A(2)^{n} + B(-1)^{n}

Now, imagine our initial conditions are

F_{0} = 1 and F_{1} = 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

F_{n} = (2/3)2^{n} + (2/3)(-1)^{n}