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.