View source for Generalizations of Fibonacci numbers

{{Short description|Mathematical sequences}}
In [[mathematics]], the [[Fibonacci number]]s form a [[sequence]] defined [[recursion|recursively]] by:
:<math>F_n =
\begin{cases}
0 & n = 0 \\
1 & n = 1 \\
F_{n - 1} + F_{n - 2} & n > 1
\end{cases}</math>

That is, after two starting values, each number is the sum of the two preceding numbers.

The Fibonacci sequence has been studied extensively and generalized in many ways, for example, by starting with other numbers than 0 and 1, by adding more than two numbers to generate the next number, or by adding objects other than numbers.

==Extension to negative integers==
Using <math>F_{n-2} = F_n - F_{n-1}</math>, one can extend the Fibonacci numbers to negative [[integer]]s. So we get:
:... −8, 5, −3, 2, −1, 1, 0, 1, 1, 2, 3, 5, 8, ...
and <math>F_{-n} = (-1)^{n + 1} F_n</math>.<ref>Triana, Juan. [http://www.viam.science.tsu.ge/others/ticmi/blt/vol23_1/3_triana.pdf Negafibonacci numbers via matrices. Bulletin of TICMI], 2019, pp.&nbsp;19–24.</ref>

See also [[Negafibonacci coding]].

==Extension to all real or complex numbers==
There are a number of possible generalizations of the Fibonacci numbers which include the [[real number]]s (and sometimes the [[complex number]]s) in their domain.  These each involve the [[golden ratio]] {{mvar|φ}}, and are based on [[Binet's formula]]
:<math>F_n = \frac{\varphi^n - (-\varphi)^{-n}}{\sqrt{5}}.</math>

The [[analytic function]]

:<math>\operatorname{Fe}(x) = \frac{\varphi^x - \varphi^{-x}}{\sqrt{5}}</math>

has the property that <math>\operatorname{Fe}(n) = F_n</math> for [[parity (mathematics)|even]] integers <math>n</math>.<ref>{{Cite web |date=2009-10-27 |title=What is a Fibonacci Number? -- from Harry J. Smith |url=http://geocities.com/hjsmithh/Fibonacc/FibWhat.html |access-date=2022-04-12 |website= |archive-url=https://web.archive.org/web/20091027103713/http://geocities.com/hjsmithh/Fibonacc/FibWhat.html |archive-date=27 October 2009 |url-status=dead}}</ref> Similarly, the analytic function:

:<math>\operatorname{Fo}(x) = \frac{\varphi^x + \varphi^{-x}}{\sqrt{5}}</math>

satisfies <math>\operatorname{Fo}(n) = F_n</math> for [[parity (mathematics)|odd]] integers <math>n</math>.

Finally, putting these together, the analytic function

:<math>\operatorname{Fib}(x) = \frac{\varphi^x - \cos(x \pi)\varphi^{-x}}{\sqrt{5}}</math>

satisfies <math>\operatorname{Fib}(n) = F_n</math> for all integers <math>n</math>.<ref>{{MathWorld|title=Fibonacci Number|urlname=FibonacciNumber|author=Pravin Chandra and [[Eric W. Weisstein]]}}</ref>

Since <math>\operatorname{Fib}(z + 2) = \operatorname{Fib}(z + 1) + \operatorname{Fib}(z)</math> for all complex numbers <math>z</math>, this function also provides an extension of the Fibonacci sequence to the entire complex plane. Hence we can calculate the generalized Fibonacci function of a complex variable, for example, 
:<math>\operatorname{Fib}(3+4i) \approx -5248.5 - 14195.9 i</math>

==Vector space==
The term ''Fibonacci sequence'' is also applied more generally to any [[function (mathematics)|function]] <math>g</math> from the integers to a [[field (mathematics)|field]] for which <math>g(n + 2) = g(n) + g(n + 1)</math>.  These functions are precisely those of the form <math>g(n) = F(n) g(1) + F(n - 1) g(0)</math>, so the Fibonacci sequences form a [[vector space]] with the functions <math>F(n)</math> and <math>F(n - 1)</math> as a [[basis (linear algebra)|basis]].

More generally, the range of <math>g</math> may be taken to be any [[abelian group]] (regarded as a '''Z'''-[[module (mathematics)|module]]). Then the Fibonacci sequences form a 2-dimensional '''Z'''-module in the same way.

==Similar integer sequences==

===Fibonacci integer sequences===
The 2-dimensional <math>\mathbb{Z}</math>-module of Fibonacci [[integer sequence]]s consists of all integer sequences satisfying <math>g(n + 2) = g(n) + g(n + 1)</math>.  Expressed in terms of two initial values we have: 
:<math>g(n) = F(n)g(1) + F(n-1)g(0) = g(1)\frac{\varphi^n-(-\varphi)^{-n}}{\sqrt 5}+g(0)\frac{\varphi^{n-1}-(-\varphi)^{1-n}}{\sqrt 5},</math>
where <math>\varphi</math> is the golden ratio.

The ratio between two consecutive elements [[convergent sequence|converges]] to the golden ratio, except in the case of the sequence which is constantly zero and the sequences where the ratio of the two first terms is <math>(-\varphi)^{-1}</math>.

The sequence can be written in the form
:<math>a\varphi^n+b(-\varphi)^{-n},</math>
in which <math>a = 0</math> if and only if <math>b = 0</math>.  In this form the simplest non-trivial example has <math>a = b = 1</math>, which is the sequence of [[Lucas number]]s:
:<math>L_n = \varphi^n + (-\varphi)^{- n}.</math>
We have <math>L_1 = 1</math> and <math>L_2 = 3</math>.  The properties include:
:<math>\begin{align}
\varphi^n &= \left(\frac{1+\sqrt{5}}{2}\right)^{\!n} = \frac{L(n)+F(n)\sqrt{5}}{2}, \\
L(n) &= F(n-1) + F(n+1).
\end{align}</math>

Every nontrivial Fibonacci integer sequence appears (possibly after a shift by a finite number of positions) as one of the rows of the [[Wythoff array]]. The Fibonacci sequence itself is the first row, and a shift of the Lucas sequence is the second row.<ref>{{citation
 | last = Morrison
 | first = D. R.
 | contribution = A Stolarsky array of Wythoff pairs
 | location = Santa Clara, CA
 | pages = 134–136
 | publisher = The Fibonacci Association
 | title = A Collection of Manuscripts Related to the Fibonacci Sequence
 | url = http://www.math.ucsb.edu/~drm/papers/stolarsky.pdf
 | year = 1980
 | access-date = 2012-07-15
 | archive-url = https://web.archive.org/web/20160304024024/http://www.math.ucsb.edu/~drm/papers/stolarsky.pdf
 | archive-date = 2016-03-04
 | url-status = dead
 }}.</ref>

See also [[Pisano period#Fibonacci integer sequences modulo n|Fibonacci integer sequences modulo ''n'']].

===Lucas sequences===
A different generalization of the Fibonacci sequence is the [[Lucas sequence]]s of the kind defined as follows:

:<math>\begin{align}
U(0) &= 0 \\
U(1) &= 1 \\
U(n + 2) &= P U(n + 1) - Q U(n),
\end{align}</math>

where the normal Fibonacci sequence is the special case of <math>P = 1</math> and <math>Q = -1</math>.  Another kind of Lucas sequence begins with <math>V(0) = 2</math>, <math>V(1) = P</math>. Such sequences have applications in [[number theory]] and [[prime number|primality]] proving.

When <math>Q = -1</math>, this sequence is called '''{{mvar|P}}-Fibonacci sequence''', for example, [[Pell sequence]] is also called '''2-Fibonacci sequence'''.

The '''3-Fibonacci sequence''' is
:0, 1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837, 141481, 467280, 1543321, 5097243, 16835050, 55602393, 183642229, 606529080, ... {{OEIS|id=A006190}}

The '''4-Fibonacci sequence''' is
:0, 1, 4, 17, 72, 305, 1292, 5473, 23184, 98209, 416020, 1762289, 7465176, 31622993, 133957148, 567451585, 2403763488, ... {{OEIS|id=A001076}}

The '''5-Fibonacci sequence''' is
:0, 1, 5, 26, 135, 701, 3640, 18901, 98145, 509626, 2646275, 13741001, 71351280, 370497401, 1923838285, 9989688826, ... {{OEIS|id=A052918}}

The '''6-Fibonacci sequence''' is
:0, 1, 6, 37, 228, 1405, 8658, 53353, 328776, 2026009, 12484830, 76934989, 474094764, 2921503573, 18003116202, ... {{OEIS|id=A005668}}

The '''{{mvar|n}}-Fibonacci constant''' is the ratio toward which adjacent <math>n</math>-Fibonacci numbers tend; it is also called the '''{{mvar|n}}th [[metallic mean]]''', and it is the only positive [[root of a polynomial|root]] of <math>x^2 - nx - 1 = 0</math>. For example, the case of <math>n = 1</math> is <math>\frac{1 + \sqrt{5}}{2}</math>, or the [[golden ratio]], and the case of <math>n = 2</math> is <math>1 + \sqrt{2}</math>, or the [[silver ratio]]. Generally, the case of <math>n</math> is <math>\frac{n + \sqrt{n^2 + 4}}{2}</math>.{{citation needed|reason=as the IP got it wrong, it needs a reference.  The quadratic formula does not fall under WP:CALC.|date=September 2014}}

Generally, <math>U(n)</math> can be called '''{{math|(''P'',−''Q'')}}-Fibonacci sequence''', and {{math|''V''(''n'')}} can be called '''{{math|(''P'',−''Q'')}}-Lucas sequence'''.

The '''(1,2)-Fibonacci sequence''' is
:0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101, 2796203, 5592405, 11184811, 22369621, 44739243, 89478485, ... {{OEIS|id=A001045}}

The '''(1,3)-Fibonacci sequence''' is
:1, 1, 4, 7, 19, 40, 97, 217, 508, 1159, 2683, 6160, 14209, 32689, 75316, 173383, 399331, 919480, 2117473, 4875913, 11228332, 25856071, 59541067, ... {{OEIS|id=A006130}}

The '''(2,2)-Fibonacci sequence''' is
:0, 1, 2, 6, 16, 44, 120, 328, 896, 2448, 6688, 18272, 49920, 136384, 372608, 1017984, 2781184, 7598336, 20759040, 56714752, ... {{OEIS|id=A002605}}

The '''(3,3)-Fibonacci sequence''' is
:0, 1, 3, 12, 45, 171, 648, 2457, 9315, 35316, 133893, 507627, 1924560, 7296561, 27663363, 104879772, 397629405, 1507527531, 5715470808, ... {{OEIS|id=A030195}}

===Fibonacci numbers of higher order===

A '''Fibonacci sequence of order {{mvar|n}}''' is an integer sequence in which each sequence element is the sum of the previous <math>n</math> elements (with the exception of the first <math>n</math> elements in the sequence). The usual Fibonacci numbers are a Fibonacci sequence of order 2. The cases <math>n = 3</math> and <math>n = 4</math> have been thoroughly investigated. The number of [[Composition (number theory)|compositions]] of nonnegative integers into parts that are at most <math>n</math> is a Fibonacci sequence of order <math>n</math>. The sequence of the number of strings of 0s and 1s of length <math>m</math> that contain at most <math>n</math> consecutive 0s is also a Fibonacci sequence of order <math>n</math>.

These sequences, their limiting ratios, and the limit of these limiting ratios, were investigated by [[Mark Barr]] in 1913.<ref>{{cite book
|last=Gardner|first=Martin|author-link=Martin Gardner
|page=101|title=The Scientific American Book of Mathematical Puzzles and Diversions, Vol. II
|publisher=Simon and Schuster|year=1961}}</ref>

==== Tribonacci 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. The first few tribonacci numbers are:
:[[0 (number)|0]], [[0 (number)|0]], [[1 (number)|1]], [[1 (number)|1]], [[2 (number)|2]], [[4 (number)|4]], [[7 (number)|7]], [[13 (number)|13]], [[24 (number)|24]], [[44 (number)|44]], [[81 (number)|81]], [[149 (number)|149]], 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, … {{OEIS|A000073}}

The series was first described formally by Agronomof<ref>{{cite journal | last1 = Tuenter | first1 = Hans J. H. | doi = 10.1080/00029890.2023.2231796 | title = In Search of Comrade Agronomof: Some Tribonacci History | journal = The American Mathematical Monthly | volume = 130 | issue = 8 | pages = 708–719 |date=October 2023| mr=4645497 }}</ref> in 1914,<ref name="agr">{{Cite journal|last=Agronomof|first=M.|year=1914|title=Sur une suite récurrente.|journal=Mathesis|volume=4|pages=125–126}}</ref> but its first unintentional use is in the ''[[On the Origin of Species|Origin of Species]]'' by [[Charles Darwin|Charles R. Darwin]]. In the example of illustrating the growth of elephant population, he relied on the calculations made by his son, [[George Darwin|George H. Darwin]].<ref name="darwinelephants">{{Cite journal | last1 = Podani | first1 = János | last2 = Kun | first2 = Ádám | last3 = Szilágyi | first3 = András |year = 2018 | title = How Fast Does Darwin's Elephant Population Grow? | journal = Journal of the History of Biology | volume = 51 | issue = 2 | pages = 259–281 | doi = 10.1007/s10739-017-9488-5| pmid = 28726021 | s2cid = 3988121 | url = http://real.mtak.hu/72652/1/Podani_etal_DarwinElephants.pdf }}</ref> The term '''tribonacci''' was suggested by Feinberg in 1963.<ref name="feinb">{{Cite journal | last = Feinberg | first = M. | year = 1963 | title = Fibonacci-Tribonacci. | journal = Fibonacci Quarterly | volume = 1 | pages = 71–74 }}</ref>

The '''tribonacci constant'''
:<math> \frac{1+\sqrt[3]{19+3\sqrt{33}}+\sqrt[3]{19-3\sqrt{33}}}{3} = \frac{1+4\cosh\left(\frac{1}{3}\cosh^{-1}\left(2+\frac{3}{8}\right)\right)}{3} \approx 1.839286755214161,</math> {{OEIS|A058265}}
is the ratio toward which adjacent tribonacci numbers tend.  It is a root of the polynomial <math>x^3 - x^2 - x - 1 = 0</math>, and also satisfies the equation <math>x + x^{-3} = 2</math>.  It is important in the study of the [[snub cube]].

[[File:TRIBONACCI.jpg|thumb|A geometric construction of the Tribonacci constant (AC), with compass and marked ruler, according to the method described by Xerardo Neira.]]

The '''reciprocal of the tribonacci constant''', expressed by the relation <math>\xi^3 + \xi^2 + \xi = 1</math>, can be written as:
:<math>\xi = \frac{\sqrt[3]{17+3\sqrt{33}} - \sqrt[3]{-17+3\sqrt{33}} - 1}{3} = \frac{3}{1 + \sqrt[3]{19 + 3\sqrt{33}} + \sqrt[3]{19-3\sqrt{33}}} \approx 0.543689012.</math> {{OEIS|A192918}}

The tribonacci numbers are also given by<ref>[http://www.plouffe.fr Simon Plouffe, 1993]</ref>

:<math>T(n) = \left\lfloor 3b\, \frac{\left(\frac{1}{3} \left( a_{+} + a_{-} + 1\right)\right)^n}{b^2-2b+4} \right\rceil</math>

where <math>\lfloor \cdot \rceil</math> denotes the [[nearest integer function]] and

:<math>\begin{align}
a_{\pm} &= \sqrt[3]{19 \pm 3 \sqrt{33}}\,, \\
b &= \sqrt[3]{586 + 102 \sqrt{33}}\,.
\end{align}</math>

==== Tetranacci numbers ====
The '''tetranacci numbers''' start with four predetermined terms, each term afterwards being the sum of the preceding four terms. The first few tetranacci numbers are:
:0, 0, 0, 1, 1, 2, 4, 8, [[15 (number)|15]], [[29 (number)|29]], [[56 (number)|56]], [[108 (number)|108]], [[208 (number)|208]], 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, … {{OEIS|A000078}}

The '''tetranacci constant''' is the ratio toward which adjacent tetranacci numbers tend.  It is a root of the polynomial <math>x^4 - x^3 - x^2 - x - 1 = 0</math>, approximately 1.927561975482925 {{OEIS|A086088}}, and also satisfies the equation <math>x + x^{-4} = 2</math>.

The tetranacci constant can be expressed in terms of [[radical expression|radicals]] by the following expression:<ref name=":0">{{Cite journal|last=Wolfram|first=D.A.|date=1998|title=Solving Generalized Fibonacci Recurrences|url=http://www.fq.math.ca/Scanned/36-2/wolfram.pdf|journal=Fib. Quart.}}</ref>

:<math>x = \frac{1}{4}\!\left(1+\sqrt{u}+\sqrt{11-u+\frac{26}{\sqrt{u}}}\,\right)</math>

where, 

:<math>u = \frac{1}{3}\left(11-56\sqrt[3]{\frac{2}{-65+3\sqrt{1689}}}+2\cdot2^{\frac{2}{3}}\sqrt[3]{-65+3\sqrt{1689}}\right) </math>

and <math>u</math> is the real root of the cubic equation <math>u^3-11u^2+115u-169.</math>

==== Higher orders ====
Pentanacci, hexanacci, heptanacci, octanacci and enneanacci numbers have been computed. 

Pentanacci numbers:
:0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, … {{OEIS|A001591}}

The '''pentanacci constant''' is the ratio toward which adjacent pentanacci numbers tend. 
It is a root of the polynomial <math>x^5 - x^4 - x^3 - x^2 - x - 1 = 0</math>, approximately 1.965948236645485 {{OEIS|A103814}}, and also satisfies the equation <math>x + x^{-5} = 2</math>.

Hexanacci numbers:
:0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, … {{OEIS|A001592}}

The '''hexanacci constant''' is the ratio toward which adjacent hexanacci numbers tend. 
It is a root of the polynomial <math>x^6 - x^5 - x^4 - x^3 - x^2 - x - 1 = 0</math>, approximately 1.98358284342 {{OEIS| A118427}}, and also satisfies the equation <math>x + x^{-6} = 2</math>.

Heptanacci numbers:
:0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, … {{OEIS|A122189}}

The '''heptanacci constant''' is the ratio toward which adjacent heptanacci numbers tend. 
It is a root of the polynomial <math>x^7 -  x^6 - x^5 - x^4 - x^3 - x^2 - x - 1 = 0</math>, approximately 1.99196419660 {{OEIS|A118428}}, and also satisfies the equation <math>x + x^{-7} = 2</math>.

Octanacci numbers:
:0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, ... {{OEIS|A079262}}

Enneanacci numbers:
:0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272, ... {{OEIS|A104144}}

The limit of the ratio of successive terms of an <math>n</math>-nacci series tends to a root of the equation <math>x + x^{-n} = 2</math> ({{OEIS2C|A103814}}, {{OEIS2C|A118427}}, {{OEIS2C|A118428}}).
 
An alternate recursive formula for the limit of ratio <math>r</math> of two consecutive <math>n</math>-nacci numbers can be expressed as
:<math>r=\sum_{k=0}^{n-1}r^{-k}</math>.

The special case <math>n = 2</math> is the traditional Fibonacci series yielding the golden section <math>\varphi = 1 + \frac{1}{\varphi}</math>.

The above formulas for the ratio hold even for <math>n</math>-nacci series generated from arbitrary numbers. The limit of this ratio is 2 as <math>n</math> increases.  An "infinacci" sequence, if one could be described, would after an infinite number of zeroes yield the sequence 
:[..., 0, 0, 1,] 1, 2, 4, 8, 16, 32, …
which are simply the [[powers of two]].

The limit of the ratio for any <math>n > 0</math> is the positive root <math>r</math> of the characteristic equation<ref name=":0" />
:<math>x^n - \sum_{i = 0}^{n-1} x^i = 0.</math> 
The root <math>r</math> is in the [[Interval (mathematics)|interval]] <math>2(1 - 2^{-n}) < r < 2</math>. The negative root of the characteristic equation is in the interval (−1, 0) when <math>n</math> is even. This root and each complex root of the characteristic equation has [[Complex number#Polar complex plane|modulus]] <math>3^{-n} < |r| < 1</math>.<ref name=":0" />

A series for the positive root <math>r</math> for any <math>n > 0</math> is<ref name=":0" />
:<math>2 - 2\sum_{i > 0} \frac{1}{i}\binom{(n+1)i -2}{i-1}\frac{1}{2^{(n+1)i}}.</math>

There is no solution of the characteristic equation in terms of radicals when {{math|5 ≤ ''n'' ≤ 11}}.<ref name=":0" />

The {{mvar|k}}th element of the {{mvar|n}}-nacci sequence is given by
:<math>F_k^{(n)} = \left\lfloor \frac{r^{k-1} (r-1)}{(n+1)r-2n}\right\rceil\!,</math>
where <math>\lfloor \cdot \rceil</math> denotes the nearest integer function and <math>r</math> is the <math>n</math>-nacci constant, which is the root of <math>x + x^{-n} = 2</math> nearest to 2.

A [[coin-tossing problem]] is related to the <math>n</math>-nacci sequence. The probability that no <math>n</math> consecutive tails will occur in <math>m</math> tosses of an idealized coin is <math>\frac{1}{2^m}F^{(n)}_{m + 2}</math>.<ref>{{MathWorld|title=Coin Tossing|urlname=CoinTossing|author=[[Eric W. Weisstein]]}}</ref>

== Fibonacci word ==
{{main|Fibonacci word}}
In analogy to its numerical counterpart, the [[Fibonacci word]] is defined by:
:<math> F_n := F(n):= \begin{cases}
\text{b}      & n = 0; \\
\text{a}      & n = 1; \\
F(n-1)+F(n-2) & n > 1. \\
\end{cases}</math>
where <math>+</math> denotes the [[concatenation]] of two strings. The sequence of Fibonacci strings starts:

:{{not a typo|b, a, ab, aba, abaab, abaababa, abaababaabaab,}} … {{OEIS|id=A106750}}

The length of each Fibonacci string is a Fibonacci number, and similarly there exists a corresponding Fibonacci string for each Fibonacci number.

Fibonacci strings appear as inputs for the [[worst case]] in some computer [[algorithm]]s.

If "a" and "b" represent two different materials or atomic bond lengths, the structure corresponding to a Fibonacci string is a [[Fibonacci quasicrystal]], an aperiodic [[quasicrystal]] structure with unusual [[Spectrum (functional analysis)|spectral]] properties.

==Convolved Fibonacci sequences==
A '''convolved Fibonacci sequence''' is obtained applying a [[convolution]] operation to the Fibonacci sequence one or more times. Specifically, define<ref>V. E. Hoggatt, Jr. and M. Bicknell-Johnson, [http://www.fq.math.ca/Scanned/15-2/hoggatt1.pdf "Fibonacci Convolution Sequences"], ''Fib. Quart.'', 15 (1977), pp. 117-122.</ref>

:<math>F_n^{(0)}=F_n</math>
and
:<math>F_n^{(r+1)}=\sum_{i=0}^n F_i F_{n-i}^{(r)}</math>

The first few sequences are
:<math>r = 1</math>: 0, 0, 1, 2, 5, 10, 20, 38, 71, … {{OEIS|A001629}}.
:<math>r = 2</math>: 0, 0, 0, 1, 3, 9, 22, 51, 111, … {{OEIS|A001628}}.
:<math>r = 3</math>: 0, 0, 0, 0, 1, 4, 14, 40, 105, … {{OEIS|A001872}}.

The sequences can be calculated using the recurrence
:<math>F_{n+1}^{(r+1)}=F_n^{(r+1)}+F_{n-1}^{(r+1)}+F_n^{(r)}</math>

The [[generating function]] of the <math>r</math>th convolution is 
:<math>s^{(r)}(x)=\sum_{k=0}^{\infty} F^{(r)}_n x^n=\left(\frac{x}{1-x-x^2}\right)^r.</math>

The sequences are related to the sequence of [[Fibonacci polynomials]] by the relation
:<math>F_n^{(r)}=r! F_n^{(r)}(1)</math>
where <math>F^{(r)}_n(x)</math> is the <math>r</math>th [[derivative]] of <math>F_n(x)</math>. Equivalently, <math>F^{(r)}_n</math> is the [[coefficient]] of <math>(x - 1)^r</math> when <math>F_x(x)</math> is expanded in powers of <math>(x - 1)</math>.

The first convolution, <math>F^{(1)}_n</math> can be written in terms of the Fibonacci and Lucas numbers as
:<math>F_n^{(1)}=\frac{nL_n-F_n}{5}</math>
and follows the recurrence
:<math>F_{n+1}^{(1)}=2F_n^{(1)}+F_{n-1}^{(1)}-2F_{n-2}^{(1)}-F_{n-3}^{(1)}.</math>
Similar expressions can be found for <math>r > 1</math> with increasing complexity as <math>r</math> increases. The numbers <math>F^{(1)}_n</math> are the row sums of [[Hosoya's triangle]].

As with Fibonacci numbers, there are several combinatorial interpretations of these sequences. For example <math>F^{(1)}_n</math> is the number of ways <math>n - 2</math> can be written as an ordered sum involving only 0, 1, and 2 with 0 used exactly once. In particular <math>F^{(1)}_4 = 5</math> and 2 can be written {{nowrap|0 + 1 + 1}}, {{nowrap|0 + 2}}, {{nowrap|1 + 0 + 1}}, {{nowrap|1 + 1 + 0}}, {{nowrap|2 + 0}}.<ref>{{Cite OEIS|sequencenumber=A001629}}</ref>

==Other generalizations==
The [[Fibonacci polynomials]] are another generalization of Fibonacci numbers.

The [[Padovan sequence]] is generated by the recurrence <math>P(n) = P(n - 2) + P(n - 3)</math>.

The [[Supergolden_ratio#Narayana sequence|Narayana's cows]] sequence is generated by the recurrence <math>N(k) = N(k - 1) + N(k - 3)</math>.

A '''random Fibonacci sequence''' can be defined by tossing a coin for each position <math>n</math> of the sequence and taking <math>F(n) = F(n - 1) + F(n - 2)</math> if it lands heads and <math>F(n) = F(n - 1) - F(n - 2)</math> if it lands tails.  Work by Furstenberg and Kesten guarantees that this sequence [[almost surely]] [[grows exponentially]] at a constant rate: the constant is independent of the coin tosses and was computed in 1999 by [[Divakar Viswanath]].  It is now known as [[Viswanath's constant]].

A '''repfigit''', or '''[[Keith number]]''', is an integer such that, when its digits start a Fibonacci sequence with that number of digits, the original number is eventually reached.  An example is 47, because the Fibonacci sequence starting with 4 and 7 {{nowrap|(4, 7, 11, 18, 29, 47)}} reaches 47.  A repfigit can be a tribonacci sequence if there are 3 digits in the number, a tetranacci number if the number has four digits, etc. The first few repfigits are:
:14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, 7385, 7647, 7909, … {{OEIS|A007629}}

Since the set of sequences satisfying the relation <math>S(n) = S(n - 1) + S(n - 2)</math> is closed under termwise addition and under termwise multiplication by a constant, it can be viewed as a [[vector space]].  Any such sequence is uniquely determined by a choice of two elements, so the vector space is two-[[dimension (vector space)|dimensional]].  If we abbreviate such a sequence as <math>(S(0), S(1))</math>, the Fibonacci sequence <math>F(n) = (0, 1)</math> and the shifted Fibonacci sequence <math>F(n - 1) = (1, 0)</math> are seen to form a canonical basis for this space, yielding the identity:

:<math>S(n) = S(0) F(n-1) + S(1) F(n)</math>

for all such sequences {{mvar|S}}.  For example, if {{mvar|S}} is the Lucas sequence {{nowrap|2, 1, 3, 4, 7, 11, ...}}, then we obtain
:<math>L(n) = 2F(n-1) + F(n)</math>.

==={{mvar|N}}-generated Fibonacci sequence===
We can define the '''{{mvar|N}}-generated Fibonacci sequence''' (where {{mvar|N}} is a positive [[rational number]]): if
:<math>N = 2^{a_1}\cdot 3^{a_2}\cdot 5^{a_3}\cdot 7^{a_4}\cdot 11^{a_5}\cdot 13^{a_6}\cdot \ldots \cdot p_r^{a_r},</math>
where {{mvar|p<sub>r</sub>}} is the {{mvar|r}}th prime, then we define
:<math>F_N(n) = a_1F_N(n-1) + a_2F_N(n-2) + a_3F_N(n-3) + a_4F_N(n-4) + a_5F_N(n-5) + ...</math>
If <math>n = r - 1</math>, then <math>F_N(n) = 1</math>, and if <math>n < r - 1</math>, then <math>F_N(n) = 0</math>.{{citation needed|reason=has this been defined outside of this article?|date=June 2019}}

:{|class="wikitable"
!Sequence
!{{mvar|N}}
![[OEIS]] sequence
|-
|Fibonacci sequence
|6
|{{OEIS link|id=A000045}}
|-
|Pell sequence
|12
|{{OEIS link|id=A000129}}
|-
|[[Jacobsthal number|Jacobsthal sequence]]
|18
|{{OEIS link|id=A001045}}
|-
|Narayana's cows sequence
|10
|{{OEIS link|id=A000930}}
|-
|Padovan sequence
|15
|{{OEIS link|id=A000931}}
|-
|[[Supersilver ratio#Third-order Pell sequences|Third-order Pell sequence]]
|20
|{{OEIS link|id=A008998}}
|-
|Tribonacci sequence
|30
|{{OEIS link|id=A000073}}
|-
|Tetranacci sequence
|210
|{{OEIS link|id=A000288}}
|}

===Semi-Fibonacci sequence===
The '''semi-Fibonacci sequence''' {{OEIS|A030067}} is defined via the same recursion for odd-indexed terms <math> a(2n+1) = a(2n) + a(2n-1)</math> and <math>a(1) = 1</math>, but for even indices <math> a(2n) = a(n)</math>, <math>n \ge 1</math>. The bisection {{OEIS link|id=A030068}} of odd-indexed terms <math>s(n) = a(2n-1)</math> therefore verifies <math>s(n+1) = s(n) + a(n)</math> and is [[Sequence#Increasing and decreasing|strictly increasing]]. It yields the set of the ''semi-Fibonacci numbers''
: 1, 2, 3, 5, 6, 9, 11, 16, 17, 23, 26, 35, 37, 48, 53, 69, 70, 87, 93, 116, 119, 145, 154, ... {{OEIS|A030068}}
which occur as <math>s(n) = a(2^k(2n-1)), k=0,1,...\, .</math>

==References==
{{reflist|2}}

==External links==
* {{springer|title=Tribonacci number|id=p/t130190}}

{{Fibonacci}}

[[Category:Fibonacci numbers]]