On Fibonacci-style Sequences

The Fibonacci sequence F_0, F_1, F_2, \dots which begins 0, 1, 1, 2, 3, 5, \dots is defined by

F_{0} = 0

F_{1} = 1

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

(the starting values vary by author).

This is a special case of a more general sequence given by

a_{0}

a_{1}

a_{n+2} = b \cdot a_{n} + c \cdot a_{n+1}

There are at least three ways to determine such a sequence. I explore those here.

A Fibonacci-style sequence is determined by any of:

  • The first four terms: a_0, a_1, a_2, a_3
  • The recurrence constants: a_0, a_1, b, c
  • The closed-form constants: p, q, r, s where a_n = p \cdot r^n + q \cdot s^n

These are related as follows:

a_n = p \cdot r^n + q \cdot s^n (for n \in {0,1,2,3})

b = \dfrac{{a_2}^2 - a_1 \cdot a_3}{a_0 \cdot a_2 - {a_1}^2}

c = \dfrac{a_0 \cdot a_3 - a_1 \cdot a_2}{a_0 \cdot a_2 - {a_1}^2}

r, s = \dfrac {c \pm \sqrt{c^2 + 4b}}{2}

p = \dfrac{a_1 - a_0 \cdot s}{r - s}

q = \dfrac{a_1 - a_0 \cdot r}{s - r}

The derivation of the formulae for p, q, r, s is as follows:

a_0 = p + q

a_1 = p r + q s

a_2 = p r^2 + q s^q = b a_0 + c a_1

so

p = a_0 - q = (a_1 - q s) / r = (a_2 - q s^2) / r^2

so

r p = r (a_0 - q) = a_1 - q s

r^2 p = r^2 (a_0 - q) = a_2 - q s^2

so

r a_0 - a_1 = q (r - s)

r^2 a_0 - a_2 = q (r^2 - s^2) = q (r - s)(r + s)

so

q (r - s) = r a_0 - a_1 = (r^2 a_0 - a_2) / (r + s)

so

(r + s)(r a_0 - a_1) = r^2 a_0 - a_2

but

(r + s)(r a_0 - a_1) = r^2 a_0 + r s a_0 - r a_1 - s a_1

so

0 = r s a_0 - (r + s) a_1 + a_2

but

0 = b a_0 + c a_1 - a_2

 so, identifying coefficients, (and noting symmetry for later)

b = - r s

c = r + s

so

r = -b / s

so

c = -b/s + s

so, multiplying by s

0 = s^2 - c s - b

so, by symmetry

r, s = \dfrac {c \pm \sqrt{c^2 + 4b}}{2}

and the formulae for p, q also follow.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: