Hans Walser, [20260525]

Binet's Formula

1 What it's about

Generalization of Binet's formula.

2 Problem

Given a sequence f_n with the generalized Fibonacci recursion

(1) f_n = p f_n–1 + q f_n–2

and the arbitrary starting values f₁ and f₂.

We look for an explicit formula for calculating f_n as a function of n.

3 Solution

We define:

(2) c₁ = (p + √(p² + 4q))/2, c₂ = (p – √(p² + 4q))/2

These are the two solutions of the quadratic equation c² – p c – q = 0 for c.

We make the following approach:

(3) f_n = a c₁ⁿ + b c₂ⁿ

We therefore form a linear combination of the two geometric sequences c₁ⁿ and c₂ⁿ, both of which satisfy recursion (1).

To calculate the coefficients a and b, we use the initial values f₁ and f2. We obtain the linear system of equations:

(4) f₁ = a c₁¹ + b c₂¹

f₂ = a c₁² + b c₂²

We substitute the solutions a and b into (3). This is the explicit formula we are looking for.

4 Examples

For p = 1, q = 1, f₁ = 1, and f₂ = 1, we get the classic Fibonacci sequence (Table 1).

n	fn
1	1
2	1
3	2
4	3
5	5
6	8
7	13
8	21
9	34
10	55

Tab. 1: Classical Fibonacci sequence

For p = 1, q = –1, f₁ = 3, and f₂ = 4, we get a periodic sequence (Table 2). It is antiperiodic with a period of 3 and periodic with a period of 6.

n	fn
1	3
2	4
3	1
4	–3
5	–4
6	–1
7	3
8	4
9	1
10	–3

Tab. 2: Periodic sequence

For p = i, q = 1, f₁ = 3, and f₂ = 4, we get a periodic sequence with complex numbers (Table 3). It is antiperiodic with a period of 6 and periodic with a period of 12. Furthermore, f_n+3 = if_n.

1	3
2	4
3	3 + 4i
4	3i
5	4i
6	–4 + 3i
7	–3
8	–4
9	–3 – 4i
10	–3i
11	–4i
12	4 – 3i
13	3
14	4
15	3 + 4i
16	3i
17	4i
18	–4 + 3i
19	–3
20	–4

Tab. 3: Complex values