Non-Recursive Formula

Date: 06/05/2001 at 10:38:01
From: Dang Nguyen Duc
Subject: General Fibonacci Sequence

I want to know the non-recursive formula of the nth number in the 
general Fibonacci sequence. The general Fibonacci sequence is:

  F(n+k) = a1*F(n+k-1)+a2*F(n+k-2)+...+ak*F(n)

I know that we can get it by solving this equation:

  x^k-a1*x^(k-1)-...-ak = 0

Could you explain why we come to this conclusion? Thanks.
Dang Nguyen Duc

Date: 06/05/2001 at 17:11:54
From: Doctor Rob
Subject: Re: General Fibonacci Sequence

Thanks for writing to Ask Dr. Math.

If k = 1, you would have

   F(n+1) = a1*F(n).

The solution to this is ("obviously")

   F(n) = c1*a1^n,

for any constant c1. Also a1 is a root of the polynomial equation
x - a1 = 0.

Now suppose that

   F(n) = c1*r^n + c2*s^n,

where alpha and beta are not equal. What equation would this satisfy?

   F(n+2) = c1*r^(n+2) + c2*s^(n+2),
          = c1*r^(n+1)*r + c2*s^(n+1)*s,
          = c1*r^(n+1)*(r+s) + c1*(-r*s)*r^n +
              c2*s^(n+1)*(r+s) + c2*(-r*s)*s^n,
          = (r+s)*F(n+1) + (-r*s)*F(n+2).

Thus if we set

   r + s = a1,
   -r*s = a2,

then F(n) will satisfy the recursion

   F(n+2) = a1*F(n+1) + a2*F(n).

Now r and s are the roots of the equation

   (x-r)*(x-s) = 0,
   x^2 - (r+s)*x - (-r*s) = 0,
   x^2 - a1*x - a2 = 0.

Thus the solution of the recursion

   F(n+2) = a1*F(n+1) + a2*F(n)

is given by

   F(n) = c1*r^n + c2*s^n,

for any constants c1 and c2, where r and s are distinct roots of the
polynomial equation

   x^2 - a1*x - a2 = 0.

The constants c1 and c2 are determined by the initial conditions on
F(n).  The same situation holds for a linear combination of k > 2
unequal exponential functions, except the degree of the equation is k.
The coefficients of the equation are just the ones appearing in the
recursion.  (One has to make an adjustment to handle the case when the
polynomial equation has repeated roots.)

Another way to see this is to express the recursion in terms of the
shift operator S which operates on sequences:

   S(F[n]) = F(n+1).

Then the recursion can be rewritten in the form

   S^k(F[n]) - a1*S^(k-1)(F[n]) - ... - ak*F(n) = 0,

or

   (S^k - a1*S^[k-1] - ... - ak)(F[n]) = 0.

This says that the sequence F(n) is annihilated by the operator in
parentheses.  Now if this polynomial in S has distinct roots r1, r2,
..., rk, then (because S commutes with multiplication by constants) it
can be factored into

   ([S-r1]*[S-r2]*...*[S-rk])(F[n]) = 0.

Now the operator S - rk annihilates the sequence rk^n, and multiplies
ri^n by a nonzero constant ri - rk.  This means that applying these
operators S - ri for i = k, k-1, ..., 2, 1 annihilates any linear
combination of these exponential functions.  (Again, if the polynomial
has repeated roots, there is an adjustment which needs to be made.)
Thus a set of solutions of this equation is

   F(n) = c1*r1^n + c2*r2^n + ... + ck*rk^n,

for any constants c1, ..., ck.  These constants are determined by the
initial conditions on F(n).

That this is all the solutions can be seen by the fact that the
dimension k of the space of solutions is equal to the dimension k of
this set of solutions, so this set is all there is.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/