Wave sequences.


The famous Fibonacci sequence can be generalized in several ways. One way is to see it as a wave sequence.

Nederlandse versie van deze pagina.


Wave sequences

A wave sequence is made following a very simple algorithm. As an example let us start to create a 2-wave sequence, i.e. a wave sequence of amplitude 2.

A 2-wave sequence will consist of numbers positioned in the following way:

* * * * * *    etc.
 * * * * * *

As a start we fill in the first two numbers. For example, let them both be 1. All other numbers are found by adding the preceding number and the number left to it:

1 2 5 13 34 89 etc.
 1 3 8 21 55

As you see, we find the famous Fibonacci sequence here.

However, the 3-wave sequence looks less familiar:

1   3    14      70         353
 1 2 5 11  25  56  126   283       Etc.
  1   6      31       157

When we look more precisely to this sequence, we find that sequence formed by dropping the middle line of the wave

 1 1 3 6 14 31 70 157

is a known sequence, described by Jacques Haubrich in the Dutch journal for mathematics teachers "Euclides" as the number of paths with n reflections through 3 glass-plates. A recurrence formula for this sequence is a(n)= 2a(n-1)+a(n-2)-a(n-3). In fact it turns out that the middle row of this 3-wave sequence fullfills the same recurrence formula. So for the 3-wave we find the recurrence formula: a(n)=2a(n-2)+a(n-4)-a(n-6).

The 4-wave sequence

The 4-wave sequence reads

1     4        30            246
 1   3 7     26  56       216       Etc.
  1 2   9  19      75  160
   1     10          85

Again, dropping the 2 middle lines give the sequence of paths through four glass plates. They are given by the recurrence formula a(n)=2a(n-1)+3a(n-2)-a(n-3)-a(n-4). And again we can extend this to a recurrence formula for the 4-wave sequence:

a(n)= 2a(n-3)+3a(n-6)-a(n-9)-a(n-12).

How to find these recurrence formulae?

The recurrence formulae we found for 3-wave and 4-wave sequences seemed to drop out of the air. We can derive these formulae in quite an easy way.

To do this, we consider, as an example, the 4-wave sequence. We divide the sequence in vectors in the following way.

The first vector is made out of the first 4 numbers:

1     4        30            246
 1   3 7     26  56       216 
  1 2   9  19      75  160
   1     10          85

This gives the vector .

The second vector is made out of the fourth to seventh number

1     4        30            246
 1   3 7     26  56       216       Etc.
  1 2   9  19      75  160
   1     10          85

And this gives the vector . And we can go on finding , , etc.

From the description on how to compute the numbers in a wave sequence, we can derive that we can find the next vector from a given vector by multiplying by matrix

M = .

The characteristic equation of this matrix is given by k4 - 2k3 - 3k2 + k + 1 = 0. From the Cayley-Hamilton Theorem we know that matrix M is anihilated by its own characteristic polynomial, so that M4 = 2M3 + 3M2 - M - 1.

This means that the vector found after multiplying by M4 can be found also by applying 2M3 + 3M2 - M - 1 instead. This immediatly explains the recursion formula a(n)=2a(n-3)+3a(n-6)-a(n-9)-a(n-12).


Back to Floors wiskunde pagina (Dutch).

Home (Dutch).