(Redirected from Binary Fibonacci rabbits sequence)
![Pending changes are displayed on this page Pending changes are displayed on this page](/w/extensions/FlaggedRevs/frontend/modules/img/1.png)
There are no approved revisions of this page, so it may
not have been
reviewed.
This article needs more work.
Please help by expanding it!
There are a number of ways of keeping track of the population of "[male-female] pairs of Fibonacci rabbits" pertaining to the Fibonacci numbers.
Tree of "[male-female] pairs of Fibonacci rabbits"
Tree of newborn (0) and mature (1) "[male-female] pairs of Fibonacci rabbits"
0
1
1
0
1
0
1
1
0
1
1
0
1
0
1
1
0
1
0
1
|
|
|
|
Tree of newborn (0 months old) and mature (≥ 1 months old) "[male-female] pairs of Fibonacci rabbits"
0
1
2
0
3
0
1
4
0
1
2
0
5
0
1
2
0
3
0
1
|
|
|
|
The Fibonacci rabbits tree (more precisely, the tree of [male-female] pairs of Fibonacci rabbits), named after Leonardo of Pisa (known as Fibonacci), follows the rules:
- at the beginning of the 0 th month, there are no rabbits on the island;
- at the beginning of the 1st month, a [male-female] pair of newborn rabbits is dropped on the island;
- thereafter, at the beginning of each month,
- every [male-female] pair of newborn rabbits becomes a [male-female] pair of mature rabbits,
- every [male-female] pair of mature rabbits begets a [male-female] pair of newborn rabbits, where the offspring stands to the right of the parents;
where
- a [male-female] pair of newborn rabbits (red vertex) is represented either by 0 (mature = FALSE, left side tree) or by an age equal to 0 month (right side tree);
- a [male-female] pair of mature rabbits (green vertex) is represented either by 1 (mature = TRUE, left side tree) or by an age greater than 0 month (right side tree);
- rabbits never die.
The number of rabbits at the beginning of each month gives the
Fibonacci numbers (
A000045 )
- {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, 1346269, 2178309, 3524578, ...}
If any
[male-female] pair of rabbits could beget a new
[male-female] pair of rabbits, we would have 0 followed by
pairs at the beginning of the
th month (
A131577 )
- {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, ...}
A131577 @opsp@−@opsp@
A000045 , i.e. the number of non-existing
[male-female] pair of rabbits due to the maturation delay (0 followed by
A027934 )
- {0, 0, 1, 2, 5, 11, 24, 51, 107, 222, 457, 935, 1904, 3863, 7815, 15774, 31781, 63939, 128488, 257963, 517523, 1037630, 2079441, 4165647, 8342240, 16702191, 33433039, ...}
Binary sequence of "[male-female] pairs of Fibonacci rabbits"
The tree of newborn (0) and mature (1) "[male-female] pairs of Fibonacci rabbits" yields the
binary sequence of "[male-female] pairs of Fibonacci rabbits" (
A036299 )
- {0, 1, 10, 101, 10110, 10110101, 1011010110110, 101101011011010110101, 1011010110110101101011011010110110, 1011010110110101101011011010110110101101011011010110101, ...}
A005203 Fibonacci rabbits numbers (or rabbit sequence) converted to decimal,
.
- {0, 1, 2, 5, 22, 181, 5814, 1488565, 12194330294, 25573364166211253, 439347050970302571643057846, 15829145720289447797800874537321282579904181, ...}
Sequence of "[male-female] pairs of Fibonacci rabbits"
The tree of newborn (0 month old) and mature (≥ 1 months old) "[male-female] pairs of Fibonacci rabbits" yields the infinite sequence of finite sequences
- {{0}, {1}, {2, 0}, {3, 0, 1}, {4, 0, 1, 2, 0}, {5, 0, 1, 2, 0, 3, 0, 1}, {6, 0, 1, 2, 0, 3, 0, 1, 4, 0, 1, 2, 0}, {7, 0, 1, 2, 0, 3, 0, 1, 4, 0, 1, 2, 0, 5, 0, 1, 2, 0, 3, 0, 1}, ...}
whose concatenation yields the
sequence of "[male-female] pairs of Fibonacci rabbits" (
A035614 )
- {0, 1, 2, 0, 3, 0, 1, 4, 0, 1, 2, 0, 5, 0, 1, 2, 0, 3, 0, 1, 6, 0, 1, 2, 0, 3, 0, 1, 4, 0, 1, 2, 0, 7, 0, 1, 2, 0, 3, 0, 1, 4, 0, 1, 2, 0, 5, 0, 1, 2, 0, 3, 0, 1, ...}
Substitution rules
Substitution rule for the binary sequence of "[male-female] pairs of Fibonacci rabbits"
The Fibonacci rabbits binary sequence (more precisely, the binary sequence of [male-female] pairs of Fibonacci rabbits) is defined by the initial conditions:
- ; (the empty string: there are no rabbits on the island)
- ; (a [male-female] pair of newborn rabbits is dropped on the island)
and the substitution rules, for
:
- (a [male-female] pair of newborn rabbits becomes a [male-female] pair of mature rabbits);
- (a [male-female] pair of mature rabbits begets a [male-female] pair of newborn rabbits, where the offspring stands to the right of the parents);
where
- a [male-female] pair of newborn rabbits is represented by 0 (i.e. mature = FALSE);
- a [male-female] pair of mature rabbits is represented by 1 (i.e. mature = TRUE).
Substitution rule for the sequence of "[male-female] pairs of Fibonacci rabbits"
The Fibonacci rabbits sequence (more precisely, the sequence of [male-female] pairs of Fibonacci rabbits) is defined by the initial conditions:
- ; (the empty string: there are no rabbits on the island)
- ; (a [male-female] pair of newborn rabbits, i.e. 0 month old, is dropped on the island)
and the substitution rules, for
:
- where is the successor of (a [male-female] pair of newborn rabbits becomes a [male-female] pair of mature rabbits, i.e. more than 0 month old);
- for , where is the successor of (a [male-female] pair of mature rabbits begets a [male-female] pair of newborn rabbits, where the parent's age increases by 1 month, and where the offspring stands to the right of the parents).
"[male-female] pairs of Fibonacci rabbits" per generation
The number of [male-female] pairs of Fibonacci rabbits per generation are expressed by the Fibonacci polynomials.
The infinite Fibonacci word
A005614 The infinite Fibonacci word (start with 1, apply 0 -> 1, 1 -> 10, iterate, take limit).
- {1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, ...}
Properties
Theorem.
The th term, , of the binary Fibonacci rabbits sequence may be obtained by the concatenation of the th term and [appended by] the th term.
Proof. (by induction)
(Using . (dot) as the concatenation operator.)
Base case:
and a(3) = 10 = 1 . 0 = a(2) . a(1) |
;
Inductive step:
Assume the truth of a(k) = a(k − 1) . a(k − 2) |
for ;
then we have to show that this implies a(n) = a(n − 1) . a(n − 2) |
... □
Thus, using . (dot) as the concatenation operator
![{\displaystyle a(n)=a(n-0)\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/1dc10cb511e72b1885245935c3f40b50e5481e4a)
![{\displaystyle a(n)=a(n-1)\,.\,a(n-2)\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/bec0c1bc667ee1b3f684133883e8bd81e4e92d45)
![{\displaystyle a(n)=a(n-2)\,.\,a(n-3)\,.\,a(n-3)\,.\,a(n-4)\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/d1d7c1318b2f23a941da9928494d647aa4bcbcf2)
![{\displaystyle a(n)=a(n-3)\,.\,a(n-4)\,.\,a(n-4)\,.\,a(n-5)\,.\,a(n-4)\,.\,a(n-5)\,.\,a(n-5)\,.\,a(n-6)\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/247c0a498bbe9701a61d39bf7f7fc5361637f818)
- ...
which suggests the infinite sequence of finite sequences
- {{0}, {1, 2}, {2, 3, 3, 4}, {3, 4, 4, 5, 4, 5, 5, 6}, {4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}, {5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 9, 8, 9, 9, 10}, ...}
whose concatenation gives (matches (proof?) A014701 Number of multiplications to compute n-th power by method of Chandra-sutra.)
- {0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 9, 8, 9, 9, 10, ...}
Equivalently
![{\displaystyle a(n)=a(n-1)\,2^{1+\lfloor \log _{2}(a(n-2))\rfloor }+a(n-2)=a(n-1)\,2^{F(n-2)}+a(n-2),\quad n\geq 2.\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/b79f8617c40d95e2a7a2e5c8c287be647cf096e9)
Asymptotic behavior
![{\displaystyle {\frac {a(n)}{a(n-1)}}\sim 2^{F(n-2)}\sim 2^{\{{\frac {\phi ^{n-2}}{\sqrt {5}}}\}}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/ceb22dbe00c805716f54730dd39a026555a7c95d)
![{\displaystyle a(n)\sim a(n-1)\,2^{F(n)-F(n-1)}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/e0f426ffc61693f5847eb9cf8bb77c1d494627c7)
![{\displaystyle a(n)\,2^{F(n-1)}\sim a(n-1)\,2^{F(n)}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/848cda54f9ba03c9372acda57f22a7cc247949d8)
![{\displaystyle a(n)\,2^{\{{\frac {\phi ^{n-1}}{\sqrt {5}}}\}}\sim a(n-1)\,2^{\{{\frac {\phi ^{n}}{\sqrt {5}}}\}}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/577b87b5481edc9d3c0d3eb0e1ecdff670d5e727)
![{\displaystyle \{a(n)\}^{\sqrt {5}}\,2^{\{\phi ^{n-1}\}}\sim \{a(n-1)\}^{\sqrt {5}}\,2^{\{\phi ^{n}\}}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/324cb36c8062d54eaf92a6043c987be3096e6e59)
External links