Maths in a minute: N-bonacci sequences

The Fibonacci sequence is named after Leonardo Pisano Fibonacci.

Most of us have heard of the Fibonacci sequence. You start with the numbers 0 and 1 and generate subsequent terms by taking the sum of the two previous ones, giving you the infinite sequence

$0,1,1,2,3,5,8,13,21,34,55,89,144...$

The 3-bonacci sequence is a variation on this. Start with the numbers 0, 0, and 1, and generate subsequent numbers by taking the sum of the three previous terms. This gives the infinite sequence

$0,0,1,1,2,4,7,13,24,44,81,149,274,...$

The 4-bonacci sequence starts with the numbers 0,0,0, and 1. Every subsequent number is generated by taking the sum of the four previous terms:

$0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208,...$

You can see how this can be generalised further: the $N$ -bonacci sequence starts with $N-1$ zeroes followed by a 1, with subsequent terms being generated by taking the sum of the $N$ previous terms.

The traditional Fibonacci sequence corresponds to the 2-bonacci sequence. And the 1-bonacci sequence consists entirely of 1s.

N-bonacci constants

The Fibonacci sequence has a famous property. If you divide each term by the term that comes before it, you get a sequence of ratios:

$1/1, 2/1, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21, 55/34, 89/55, 144/89,...$

(This is ignoring the ratio between the first two terms because division by 0 isn't defined.) This sequence of ratios converges to the famous golden ratio,

$\phi =\frac{1+\sqrt{5}}{2}=1.61803398875...$

You can find out more about this here.

Is something similar true for other $N$ -bonacci sequences? The answer is "yes", and the corresponding limits are called $N$ -bonacci constants (or sometimes $N$ -anacci constants). Here are first five $N$ -bonacci constants:

N	N-bonacci constant
1	1
2	1.61803...
3	1.83928...
4	1.92756...
5	1.96595...

In fact, it is possible to show that for any natural number $N$ , the corresponding $N$ -anacci constant is a solution to the equation

$\begin{equation} x+\frac{1}{x^ N}=2.\end{equation}$

(1)

Such an equation always has exactly one solution which is greater than $1$ — and that’s the solution that gives you the $N$ -bonacci constant.

The infinacci sequence

We can even talk about the infinacci sequence, for which $N$ equals infinity. This starts with an infinite number of 0s, followed by a 1. The next term is the sum of the infinitely many initial 0s (which is 0) and 1, giving us a 1. Subsequent terms are

	$\displaystyle \mbox{(Sum of the infinitely many initial 0s)}$	$\displaystyle +1+1=0+1+1=2$
	$\displaystyle \mbox{(Sum of the infinitely many initial 0s)}$	$\displaystyle +1+1+2=0+1+1+2=4$
	$\displaystyle \mbox{(Sum of the infinitely many initial 0s)}$	$\displaystyle +1+1+2+4=0+1+1+2+4=8.$

Continuing on like this we see that the infinacci sequence is the sequence that starts with an infinite number of 0s followed by the powers of 2!

What about the sequence of ratios of successive terms of the infinacci sequence? Does this also have a limit? Since anything divided by 0 is undefined, let’s skip the infinitely many 0s at the start and look at the ratios between successive terms of the remaining sequence. Successive terms are always of the form $2^{k-1}$ and $2^ k$ for some natural number $k$ , so dividing a term by the one that comes before it gives $2^ k/2^{k-1}=2$ for all $k.$ Thus, the sequence of ratios of successive terms (starting after the initial zeroes) consists entirely of $2s$ , which means that its limit, what you might call the infinacci constant, is also equal to $2.$

This fits with equation (1) above. Suppose you let the $N$ in this equation tend to infinity. Then, as long as $x > 1$ (which we can assume as we are considering solutions greater than $1$ ), the term $1/x^ N$ in the equation tends to 0. This means that the solution to the equation that is greater than $1$ tends to $x=2$ .

Finally, here's another interesting bit of information. If you know about the Fibonacci sequence then you probably know that Fibonacci came up with it while thinking of a hypothetical population of rabbits (find out more here). It has been suggested that the tribonacci sequence also has an animal connection. In On the origin of species Charles Darwin considers the growth of a population of animals based on a calculation made by his son George H. Darwin — and it has been suggested that this calculation involves the tribonacci sequence.

Comments

Digital filters

It is worth noting that N-bonacci sequences have a very practical application. They form the basis of what are called FIR (finite impulse response) digital filters. These are very widely used in applications to process signals. For example your mobile phone has many digital filters in it and these make the sound much better, so that you can talk to someone a long way away without interference. The performance of the digital filter is studied using the Z-transform which is a generalisation of the methods used to give equation (1) above. The infinacci sequence arises when you study IIR or inifinite impulse response digital filters. Interstingly these can be generated without using an inifinite number of terms, but that is another (quite long) story.

Addinaccis and infinite constants

Another way we can define the Fibonacci (or 2-bonacci) sequence is A(i) = A2(i-1) - A(i-3), where i is the index or position of number A in the sequence. Any number at i in the sequence equals the one just before, i-1, multiplied by 2, minus the 3rd number back. So for example 34 = (21x2) - 8. In general an n-bonacci is defined by A(i) = A2(i-1) - A(i-(n+1)).

What if we add these two terms instead of subtracting them? What if we define an additive instead of a subtractive 3-nacci, A(i) = 2A(i-1) + A(i-4)? I got a ratio constant of about 2.1069, the positive solution to x^4 - 2x^3 - 1 = 0. In the general case of an additive n-nacci, or n-addinacci, the constant also converges on 2 but from a direction opposite to the more familiar subtractive since the 0-addinacci constant is 3 as A(i) = 2A(i-1)+ A(i-1) = 3A(i-1). The 1-addinacci (aka Pell sequence) at A(i) = 2(Ai-1) + A(Ai-2) has a constant of 2.414 (aka the Silver ratio), which is the positive solution for x^2 - 2x^1 - 1 = 0. The 2-addinacci must have the polynomial x^3 - 2x^2 - 1 = 0, and the 0-addinacci x^1 - 2x^0 - 1 = 0.

Now what about a family of sequences whose constants descend not from 3 but infinity? I suggest take the familiar Fibonacci polynomial x^2 - x- 1 = 0. The positive solution for x is here given by the fraction (1+√5)/2 ~ 1.618. Multiply just the first term of the polynomial by 2 to get the next family member 2x^2 - x - 1 = 0, and now x = (1+√9)/4 = 1. 3x^2 - x - 1 = 0 gets (1+√13)/6 ~0.768. The number under the radical increases by 4 each time, and the denominator decreases by 2. So if the first term of the polynomial is 0, as in 0x^2 + x - 1 = 0, then we should get the fraction (0 + √1)/0.

The article says anything divided by 0 is undefined, but isn't there a case for saying any natural number divided by 0 is infinity? Most of us know that the Fibonacci sequence sets out the increase in the number of rabbits that can be expected if they breed at a certain rate starting in the second month of life, in this case about 1.618 per generation, the Fibonacci constant. In rabbit breeding terms a rate of infinity means rabbits breeding more rabbits as soon as they're born, and those baby rabbits doing the same.