Fibonacci Numbers and Related Sequences

Fibonacci Numbers

These are sometimes called the Fibonacci 2-step numbers or 2-bonacci numbers. The sequence starts with two predetermined terms and each term afterwards is the sum of the preceding two terms.

\(F_0 = 0\)
\(F_1 = 1\)
\(F_n = F_{n−1} + F_{n−2}\), for integer \(n \ge 2\).

See OEIS A000045.

\\ PARI/GP
{
a = [0, 1];
for (x = 3, 30,
\(\qquad\)y = a[x – 1] + a[x – 2];
\(\qquad\)a = concat(a, y);
);
print(a);
}
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229]

Fibonacci Numbers 0–30

Base-2 (Binary)

0, 1, 1, 10, 11, 101, 1000, 1101, 10101, 100010, 110111, 1011001, 10010000, 11101001, 101111001, 1001100010, 1111011011, 11000111101, 101000011000, 1000001010101, 1101001101101, 10101011000010, 100010100101111, 110111111110001, 1011010100100000, 10010010100010001, 11101101000110001, 101111111101000010, 1001101100101110011, 1111101100010110101, 11001011001000101000

Base-3

0, 1, 1, 2, 10, 12, 22, 111, 210, 1021, 2001, 10022, 12100, 22122, 111222, 211121, 1100120, 2012011, 10112201, 12201212, 100021120, 120000102, 220021222, 1110022101, 2100121100, 10210220201, 20011112001, 100222102202, 121010221210, 222010101112, 1120021100022

Base-4

0, 1, 1, 2, 3, 11, 20, 31, 111, 202, 313, 1121, 2100, 3221, 11321, 21202, 33123, 120331, 220120, 1001111, 1221231, 2223002, 10110233, 12333301, 23110200, 102110101, 131220301, 233331002, 1031211303, 1331202311, 3023020220

Base-5

0, 1, 1, 2, 3, 10, 13, 23, 41, 114, 210, 324, 1034, 1413, 3002, 4420, 12422, 22342, 40314, 113211, 204030, 322241, 1031321, 1404112, 2440433, 4400100, 12341033, 22241133, 40132221, 112423404, 203111130

Base-6

0, 1, 1, 2, 3, 5, 12, 21, 33, 54, 131, 225, 400, 1025, 1425, 2454, 4323, 11221, 15544, 31205, 51153, 122402, 213555, 340401, 554400, 1335201, 2334001, 4113202, 10451203, 15004405, 25500012

Base-7

0, 1, 1, 2, 3, 5, 11, 16, 30, 46, 106, 155, 264, 452, 1046, 1531, 2610, 4441, 10351, 15122, 25503, 43625, 102431, 146356, 252120, 431506, 1013626, 1445435, 2462364, 4241132, 10033526

Base-8 (Octal)

0, 1, 1, 2, 3, 5, 10, 15, 25, 42, 67, 131, 220, 351, 571, 1142, 1733, 3075, 5030, 10125, 15155, 25302, 42457, 67761, 132440, 222421, 355061, 577502, 1154563, 1754265, 3131050

Base-9

0, 1, 1, 2, 3, 5, 8, 14, 23, 37, 61, 108, 170, 278, 458, 747, 1316, 2164, 3481, 5655, 10246, 16012, 26258, 43271, 70540, 123821, 204461, 328382, 533853, 863345, 1507308

Base-10 (Decimal)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040

Base-16 (Hexadecimal)

0, 1, 1, 2, 3, 5, 8, D, 15, 22, 37, 59, 90, E9, 179, 262, 3DB, 63D, A18, 1055, 1A6D, 2AC2, 452F, 6FF1, B520, 12511, 1DA31, 2FF42, 4D973, 7D8B5, CB228

Fibonacci Numbers of Higher Orders

Tribonacci Numbers

Sometimes called the Fibonacci 3-step numbers or 3-bonacci numbers, the tribonacci numbers are like the Fibonacci numbers, but instead of starting with two predetermined terms, the sequence starts with three predetermined terms and each term afterwards is the sum of the preceding three terms.

\(F_0 = F_1 = 0\)
\(F_2 = 1\)
\(F_n = F_{n−1} + F_{n−2} + F_{n−3}\), for integer \(n \ge 3\).

See OEIS A000073.

{
a = [0, 0, 1];
for (x = 4, 30,
\(\qquad\)y = a[x – 1] + a[x – 2] + a[x – 3];
\(\qquad\)a = concat(a, y);
);
print(a);
}
\(\qquad\)
[0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064]

Tetranacci numbers

Sometimes called the Fibonacci 4-step numbers or 4-bonacci numbers, the tetranacci numbers start with four predetermined terms and each term afterwards is the sum of the preceding four terms.

\(F_0 = F_1 = F_2 = 0\)
\(F_3 = 1\)
\(F_n = F_{n−1} + F_{n−2} + F_{n−3} + F_{n−4}\), for integer \(n \ge 4\).

See OEIS A000078.

{
a = [0, 0, 0, 1];
for (x = 5, 30,
\(\qquad\)y = a[x – 1] + a[x – 2] + a[x – 3] + a[x – 4];
\(\qquad\)a = concat(a, y);
);
print(a);
}
\(\qquad\)
[0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, 1055026, 2033628, 3919944, 7555935, 14564533]

Pentanacci Numbers

Sometimes called the Fibonacci 5-step numbers or 5-bonacci numbers, the pentanacci numbers start with five predetermined terms and each term afterwards is the sum of the preceding five terms.

\(F_0 = F_1 = F_2 = F_3 = 0\)
\(F_4 = 1\)
\(F_n = F_{n−1} + F_{n−2} + F_{n−3} + F_{n−4} + F_{n−5}\), for integer \(n \ge 5\).

See OEIS A001591.

{
a = [0, 0, 0, 0, 1];
for (x = 6, 30,
\(\qquad\)y = a[x – 1] + a[x – 2] + a[x – 3] + a[x – 4] + a[x – 5];
\(\qquad\)a = concat(a, y);
);
print(a);
}
\(\qquad\)
[0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, 26784, 52656, 103519, 203513, 400096, 786568, 1546352, 3040048, 5976577, 11749641]

Hexanacci Numbers

Sometimes called the Fibonacci 6-step numbers or 6-bonacci numbers, the hexanacci numbers start with six predetermined terms and each term afterwards is the sum of the preceding six terms.

\(F_0 = F_1 = F_2 = F_3 = F_4 = 0\)
\(F_5 = 1\)
\(F_n = F_{n−1} + F_{n−2} + F_{n−3} + F_{n−4} + F_{n−5} + F_{n−6}\), for integer \(n \ge 6\).

See OEIS A001592.

{
a = [0, 0, 0, 0, 0, 1];
for (x = 7, 30,
\(\qquad\)y = a[x – 1] + a[x – 2] + a[x – 3] + a[x – 4] + a[x – 5] + a[x – 6];
\(\qquad\)a = concat(a, y);
);
print(a);
}
\(\qquad\)
[0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728]

Heptanacci Numbers

Sometimes called the Fibonacci 7-step numbers or 7-bonacci numbers, the heptanacci numbers start with seven predetermined terms and each term afterwards is the sum of the preceding seven terms.

\(F_0 = F_1 = F_2 = F_3 = F_4 = F_5 = 0\)
\(F_6 = 1\)
\(F_n = F_{n−1} + F_{n−2} + F_{n−3} + F_{n−4} + F_{n−5} + F_{n−6} + F_{n−7}\), for integer \(n \ge 7\).

See OEIS ______.

{
a = [0, 0, 0, 0, 0, 0, 1];
for (x = 8, 30,
\(\qquad\)y = a[x – 1] + a[x – 2] + a[x – 3] + a[x – 4] + a[x – 5] + a[x – 6] + a[x – 7];
\(\qquad\)a = concat(a, y);
);
print(a);
}
\(\qquad\)
[0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, 31489, 62725, 124946, 248888, 495776, 987568, 1967200, 3918592]

Octanacci Numbers

Sometimes called the Fibonacci 8-step numbers or 8-bonacci numbers, the octanacci numbers start with eight predetermined terms and each term afterwards is the sum of the preceding eight terms.

\(F_0 = F_1 = F_2 = F_3 = F_4 = F_5 = F_6 = 0\)
\(F_7 = 1\)
\(F_n = F_{n−1} + F_{n−2} + F_{n−3} + F_{n−4} + F_{n−5} + F_{n−6} + F_{n−7} + F_{n−8}\), for integer \(n \ge 8\).

See OEIS ______.

{
a = [0, 0, 0, 0, 0, 0, 0, 1];
for (x = 9, 30,
\(\qquad\)y = a[x – 1] + a[x – 2] + a[x – 3] + a[x – 4] + a[x – 5] + a[x – 6] + a[x – 7]
\(\qquad\)\(\qquad\)+ a[x – 8];
\(\qquad\)a = concat(a, y);
);
print(a);
}
\(\qquad\)
[0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, 32192, 64256, 128257, 256005, 510994, 1019960, 2035872]

Enneanacci Numbers

https://oeis.org/A104144
Sometimes called the Fibonacci 9-step numbers or 9-bonacci numbers, the enneanacci numbers start with nine predetermined terms and each term afterwards is the sum of the preceding nine terms.

\(F_0 = F_1 = F_2 = F_3 = F_4 = F_5 = F_6 = F_7 = 0\)
\(F_8 = 1\)
\(F_n = F_{n−1} + F_{n−2} + F_{n−3} + F_{n−4} + F_{n−5} + F_{n−6} + F_{n−7} + F_{n−8} + F_{n−9}\), for integer \(n \ge 9\).

See OEIS ______.

{
a = [0, 0, 0, 0, 0, 0, 0, 0, 1];
for (x = 10, 30,
\(\qquad\)y = a[x – 1] + a[x – 2] + a[x – 3] + a[x – 4] + a[x – 5] + a[x – 6] + a[x – 7]
\(\qquad\)\(\qquad\)+ a[x – 8] + a[x – 9];
\(\qquad\)a = concat(a, y);
);
print(a);
}
\(\qquad\)
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272, 32512, 64960, 129792, 259328, 518145, 1035269]

Decanacci Numbers

Sometimes called the Fibonacci 10-step numbers or 10-bonacci numbers, the decanacci numbers start with 10 predetermined terms and each term afterwards is the sum of the preceding 10 terms.

\(F_0 = F_1 = F_2 = F_3 = F_4 = F_5 = F_6 = F_7 = F_8 = 0\)
\(F_9 = 1\)
\(F_n = F_{n−1} + F_{n−2} + F_{n−3} + F_{n−4} + F_{n−5} + F_{n−6} + F_{n−7} + F_{n−8} + F_{n−9} + F_{n−10}\), for integer \(n \ge 10\).

See OEIS A122265.

{
a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 1];
for (x = 11, 30,
\(\qquad\)y = a[x – 1] + a[x – 2] + a[x – 3] + a[x – 4] + a[x – 5] + a[x – 6] + a[x – 7]
\(\qquad\)\(\qquad\)+ a[x – 8] + a[x – 9] + a[x – 10];
\(\qquad\)a = concat(a, y);
);
print(a);
}
\(\qquad\)
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045, 4088, 8172, 16336, 32656, 65280, 130496, 260864, 521472]

Hendecanacci Numbers

Sometimes called the Fibonacci 11-step numbers or 11-bonacci numbers, the hendecanacci numbers start with 11 predetermined terms and each term afterwards is the sum of the preceding 11 terms.

\(F_0 = F_1 = F_2 = F_3 = F_4 = F_5 = F_6 = F_7 = F_8 = F_9 = 0\)
\(F_{10} = 1\)
\(F_n = F_{n−1} + F_{n−2} + F_{n−3} + F_{n−4} + F_{n−5} + F_{n−6} + F_{n−7} + F_{n−8} + F_{n−9} + F_{n−10} + F_{n−11}\), for integer \(n \ge 11\).

See OEIS A168082.

{
a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1];
for (x = 12, 30,
\(\qquad\)y = a[x – 1] + a[x – 2] + a[x – 3] + a[x – 4] + a[x – 5] + a[x – 6] + a[x – 7]
\(\qquad\)\(\qquad\)+ a[x – 8] + a[x – 9] + a[x – 10] + a[x – 11];
\(\qquad\)a = concat(a, y);
);
print(a);
}
\(\qquad\)
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2047, 4093, 8184, 16364, 32720, 65424, 130816, 261568]

Dodecanacci Numbers

Sometimes called the Fibonacci 12-step numbers or 12-bonacci numbers, the dodecanacci numbers start with 12 predetermined terms and each term afterwards is the sum of the preceding 12 terms.

\(F_0 = F_1 = F_2 = F_3 = F_4 = F_5 = F_6 = F_7 = F_8 = F_9 = F_{10} = 0\)
\(F_{11} = 1\)
\(F_n = F_{n−1} + F_{n−2} + F_{n−3} + F_{n−4} + F_{n−5} + F_{n−6} + F_{n−7} + F_{n−8} + F_{n−9} + F_{n−10} + F_{n−11} + F_{n−12}\), for integer \(n \ge 12\).

See OEIS A168083.

{
a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1];
for (x = 13, 30,
\(\qquad\)y = a[x – 1] + a[x – 2] + a[x – 3] + a[x – 4] + a[x – 5] + a[x – 6] + a[x – 7]
\(\qquad\)\(\qquad\)+ a[x – 8] + a[x – 9] + a[x – 10] + a[x – 11] + a[x – 12];
\(\qquad\)a = concat(a, y);
);
print(a);
}
\(\qquad\)
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4095, 8189, 16376, 32748, 65488, 130960]

Other Fibonacci Properties

Negative Fibonacci Numbers

When the Fibonacci sequence is extended in the negative direction, the numbers alternate between positive and negative.

\\ PARI/GP
for (x = -10, 10, print1(fibonacci(x), “, “))
-55, 34, -21, 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Cassini’s Formula

Cassini’s Formula states:

\(F_{n+1} \space \cdot \space F_{n-1} \space – \space (F_{n})^{2} \space = \space (-1)^{n}\)

\\ PARI/GP
for (x = 1, 10, print(x, ” = “, fibonacci(x+1) * fibonacci(x-1) – fibonacci(x)^2))
1 = -1
2 = 1
3 = -1
4 = 1
5 = -1
6 = 1
7 = -1
8 = 1
9 = -1
10 = 1

Cassini’s Formula Variant

A variant of Cassini’s Formula states:

\(F_{n-2} \space \cdot \space F_{n+1} \space – \space F_{n-1} \space \cdot \space F_{n} \space = \space (-1)^{n-1}\)

Lucas’ Theorem

Lucas’ Theorem states:

\(F_{m} \space \text{gcd} \space F_{n} \space = \space F_{(m \space \text{gcd} \space n)}\)

\(\text{gcd}\) = greatest common divisor

Simson’s Relation

Simson’s Relation states:

\(F_{n+1} \space \cdot \space F_{n-1} \space + \space (-1)^{n-1} \space = \space (F_{n})^{2}\)

References

The Fibonacci Association — Official website. Hosted by the Department of Mathematics & Statistics at Dalhousie University in Halifax, Nova Scotia, Canada. Accessed August 24, 2019.

Inglis, Alan N. “A249169 Fibonacci 16-step numbers, a(n) = a(n-1) + a(n-2) + … + a(n-16)”. The On-Line Encyclopedia of Integer Sequences (OEIS). October 22, 2014. Accessed July 21, 2019.

Sarcone, G. “Fibonacci Number Properties“. Archimedes’ Lab. 2003. Accessed August 16, 2019.

Wikipedia contributors. “Fibonacci number”. Wikipedia. Accessed July 21, 2019.

Wikipedia contributors. “Generalizations of Fibonacci numbers”. Wikipedia. Accessed July 21, 2019.

Footnotes

Leave a Reply