# Fibonacci Numbers and Related Sequences

Contents

## 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

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}$$