Generalizations of Fibonacci numbers

Template:Short description In mathematics, the Fibonacci numbers form a sequence defined recursively by:

$F_n=\{\begin{array}{cc}0& n=0\\ 1& n=1\\ F_{n-1}+F_{n-2}& n>1\end{array}$

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 Template:Tmath, one can extend the Fibonacci numbers to negative integers. So we get:

... −8, 5, −3, 2, −1, 1, 0, 1, 1, 2, 3, 5, 8, ...

and Template:Tmath.

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 numbers (and sometimes the complex numbers) in their domain. These each involve the golden ratio Template:Mvar, and are based on Binet's formula

Template:Tmath.

The analytic function

$\mathrm{Fe}(x)=\frac{{\phi }^x-{\phi }^{-x}}{\sqrt{5}}$

has the property that $\mathrm{Fe}(n)=F_n$ for even integers Template:Tmath. Similarly, the analytic function:

$\mathrm{Fo}(x)=\frac{{\phi }^x+{\phi }^{-x}}{\sqrt{5}}$

satisfies $\mathrm{Fo}(n)=F_n$ for odd integers Template:Tmath.

Finally, putting these together, the analytic function

$\mathrm{Fib}(x)=\frac{{\phi }^x-\cos (x\pi ){\phi }^{-x}}{\sqrt{5}}$

satisfies $\mathrm{Fib}(n)=F_n$ for all integers Template:Tmath.

Since $\mathrm{Fib}(z+2)=\mathrm{Fib}(z+1)+\mathrm{Fib}(z)$ for all complex numbers Template:Tmath, 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,

$\mathrm{Fib}(3+4i)\approx -5248.5-14195.9i$

However, this extension is by no means unique. For example, either

$\mathrm{Fib}(x)=\frac{{\phi }^x-\cos (kx\pi ){\phi }^{-x}}{\sqrt{5}}$ or

$\mathrm{Fib}(x)=\frac{{\phi }^x-\exp (ikx\pi ){\phi }^{-x}}{\sqrt{5}}$

for any odd integer Template:Mvar is an extension of the Fibonacci number sequence to the entire complex plane, as is any linear combination of them for which the coefficients sum to 1.

Vector space

The term Fibonacci sequence is also applied more generally to any function $g$ from the integers to a field for which Template:Tmath. These functions are precisely those of the form Template:Tmath, so the Fibonacci sequences form a vector space with the functions $F(n)$ and $F(n-1)$ as a basis.

More generally, the range of $g$ may be taken to be any abelian group (regarded as a Z-module). Then the Fibonacci sequences form a 2-dimensional Z-module in the same way.

Similar integer sequences

Fibonacci integer sequences

The 2-dimensional $\mathbb{Z}$-module of Fibonacci integer sequences consists of all integer sequences satisfying Template:Tmath. Expressed in terms of two initial values we have:

$g(n)=F(n)g(1)+F(n-1)g(0)=g(1)\frac{{\phi }^n-(-\phi {)}^{-n}}{\sqrt{5}}+g(0)\frac{{\phi }^{n-1}-(-\phi {)}^{1-n}}{\sqrt{5}},$

where $\phi$ is the golden ratio.

The ratio between two consecutive elements 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 Template:Tmath.

The sequence can be written in the form

$a{\phi }^n+b(-\phi {)}^{-n},$

in which $a=0$ if and only if Template:Tmath. In this form the simplest non-trivial example has Template:Tmath, which is the sequence of Lucas numbers:

Template:Tmath.

We have $L_1=1$ and Template:Tmath. The properties include:

$\begin{array}{cc}{\phi }^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{array}$

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.

See also Fibonacci integer sequences modulo n.

Lucas sequences

A different generalization of the Fibonacci sequence is the Lucas sequences of the kind defined as follows:

$\begin{array}{cc}U(0)& =0\\ U(1)& =1\\ U(n+2)& =PU(n+1)-QU(n),\end{array}$

where the normal Fibonacci sequence is the special case of $P=1$ and Template:Tmath. Another kind of Lucas sequence begins with Template:Tmath, Template:Tmath. Such sequences have applications in number theory and primality proving.

When Template:Tmath, this sequence is called Template:Mvar-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, ... Template:OEIS

The 4-Fibonacci sequence is

0, 1, 4, 17, 72, 305, 1292, 5473, 23184, 98209, 416020, 1762289, 7465176, 31622993, 133957148, 567451585, 2403763488, ... Template:OEIS

The 5-Fibonacci sequence is

0, 1, 5, 26, 135, 701, 3640, 18901, 98145, 509626, 2646275, 13741001, 71351280, 370497401, 1923838285, 9989688826, ... Template:OEIS

The 6-Fibonacci sequence is

0, 1, 6, 37, 228, 1405, 8658, 53353, 328776, 2026009, 12484830, 76934989, 474094764, 2921503573, 18003116202, ... Template:OEIS

The Template:Mvar-Fibonacci constant is the ratio toward which adjacent $k$-Fibonacci numbers tend; it is also called the Template:Mvarth metallic mean, and it is the only positive root of Template:Tmath. For example, the case of $k=1$ is Template:Tmath, or the golden ratio, and the case of $k=2$ is Template:Tmath, or the silver ratio. Generally, the case of $k$ is Template:Tmath.

Generally, $U(n)$ can be called Template:Math-Fibonacci sequence, and Template:Math can be called Template:Math-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, ... Template:OEIS

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, ... Template:OEIS

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, ... Template:OEIS

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, ... Template:OEIS

Fibonacci numbers of higher order

A Fibonacci sequence of order Template:Mvar, also termed Template:Mvar-nacci sequence, is an integer sequence in which each sequence element is the sum of the previous $k$ elements (with the exception of the first $k$ elements in the sequence). The usual Fibonacci numbers are a Fibonacci sequence of order 2. The number of compositions of nonnegative integers into parts that are at most $k$ is a Fibonacci sequence of order Template:Tmath. The sequence of the number of strings of 0s and 1s of length $m$ that contain at most $k$ consecutive 0s is also a Fibonacci sequence of order Template:Tmath.

These sequences, their limiting ratios, and the limit of these limiting ratios, were investigated by Mark Barr in 1913. Template:Rp

Tribonacci numbers

A variation of the Fibonacci number sequence is the tribonacci number sequence, where each number is the sum of the three preceding numbers. Starting with the initial values $T_0=T_1=0$, and $T_2=1$, the recurrence $$T_n=T_{n-1}+T_{n-2}+T_{n-3},(1)$$ gives this sequence of numbers as $$0,0,1,1,2,4,7,13,24,44,81,149,274,504,927,1705,3136,5768,10609,19513,35890,66012,\dots .$$ Further terms can be found under sequence number Template:OEIS link in The On-Line Encyclopedia of Integer Sequences (OEIS).

The tribonacci sequence has a long and interesting history. The most notable historical occurrence of the sequence is connected to Charles Darwin (1809–1882) and his seminal book On the Origin of Species, where the procreation and population growth of elephants is considered as an illustrative example. In 1892, the sequence of numbers appeared in the solution of a recreational problem, concerning a farmer and the raising of sheep, that was posed by the American mathematician Artemas Martin (1835–1918).Template:Rp The first mathematical treatment of the tribonacci sequence and an investigation of its properties was done in 1914 and is due to Agronomof. The moniker tribonacci appeared much later, not until 1963, and is due to Mark Feinberg, at the time a fourteen-year-old high-school student, who introduced the term in an article in the Fibonacci Quarterly.

Agronomof's identity. Agronomof's 1914 note is a small gem that was ignored, made no impact at the time, and gathered dust for over half a century.Template:R Although a very brief note (the modern day replica easily fits on a single pageTemplate:R), it contains the powerful identity $$T_{n+k}=T_{k+1}{T}_{n+1}+(T_k+T_{k-1})T_n+T_k{T}_{n-1}.(2)$$ Note that Agronomof's identity is symmetric in $n$ and $k$, and that, for $k=2$, one recovers the original tribonacci recurrence. Agronomof made his derivation under the assumption that both parameters $n$ and $k$ are nonnegative integers. However, one can show that the identity is more general and actually holds for arbitrary integers $n$ and $k$ by extending the defining recurrence (1) to include tribonacci numbers with negative indices.Template:R Agronomof ends his note by showcasing the following propriétés remarquables of the tribonacci numbers, $$T_{2n}=T_{n+1}^2+2T_n{T}_{n-1}+T_n^2\mathrm{a}\mathrm{n}\mathrm{d}{T}_{2n-1}=T_{n-1}^2+2T_n{T}_{n+1}-T_n^2.(3)$$ These are easily derived from his identity by taking $k=n$ and $k=n-1$. In turn, these two identities can be leveraged to derive a simple expression for the sum of squares of the tribonacci numbers.Template:R

Reflection formula. As with the Fibonacci numbers, one can run the recurrence for the tribonacci numbers backwards. From $T_2,T_1$, and $T_0$, one can determine $T_{-1}=1$. From $T_1,T_0$, and $T_{-1}$, one can determine $T_{-2}=-1$, and so on. Thus, the values for the tribonacci numbers at negative indices are well defined. Starting with $T_0=0$, $T_{-1}=1$, and $T_{-2}=-1$, and reversing the tribonacci recurrence (1), gives the sequence of negatively indexed tribonacci numbers as $$0,1,-1,0,2,-3,1,4,-8,5,7,-20,18,9,-47,56,0,-103,159,-56,-206,421,-271,-356,1048,\dots .$$ Further terms can be found under sequence number Template:OEIS link in The On-Line Encyclopedia of Integer Sequences (OEIS). The extension to negative indices means that one can view the tribonacci sequence as a double infinite sequence: $$\dots ,-47,9,18,-20,7,5,-8,4,1,-3,2,0,-1,1,\mathrm{𝟎},0,1,1,2,4,7,13,24,44,81,149,274,504,927,\dots$$ where the value at index zero is given in bold. Traversing the sequence from left to right, one uses recurrence (1). Traversing the sequence from right to left, one uses the recurrence $T_n=T_{n+3}-T_{n+2}-T_{n+1}$. The relationship between the negative and positive indexed segments of the tribonacci sequence is given by $$T_{-n}=T_{n+1}^2-T_n{T}_{n+2}.(4)$$ This identity holds for all integers $n$, and is known as the reflection formula for the tribonacci numbers. It can be derived using Agronomof's identity.Template:R

Template:Main The tribonacci constant $$\begin{array}{cc}\tau & =\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(\frac{19}{8}\right)\right)}{3}\end{array}$$ is the ratio toward which adjacent tribonacci numbers tend. It is the unique real root $x=\tau$ of the polynomial Template:Tmath, approximately Template:Val Template:OEIS, and also satisfies the equation Template:Tmath. It is important in the study of the snub cube.

Construction of the tribonacci constant with compass and marked ruler as described by Xerardo Neira. Template:Math and Template:Math.

The reciprocal of the tribonacci constant is the single real root $x=\frac{1}{\tau }$ of $x^3+x^2+x-1=0$, and can be written as $$\frac{1}{\tau }=\frac{-1+\sqrt[3]{17+3\sqrt{33}}+\sqrt[3]{17-3\sqrt{33}}}{3},$$ approximately Template:Val Template:OEIS.

The tribonacci numbers are also given by  $$T_{n+1}=\lfloor 3b\frac{{\left(\frac{1}{3}(a_{+}+a_{-}+1)\right)}^n}{b^2-2b+4}\rceil$$

where $\lfloor \cdot \rceil$ denotes the nearest integer function and $$\begin{array}{cc}{a}_{\pm }& =\sqrt[3]{19\pm 3\sqrt{33}},\\ b& =\sqrt[3]{586+102\sqrt{33}}.\end{array}$$

Corresponding to the Lucas numbers for the Fibonacci sequence, if one instead starts with $L_0=3,L_1=1\text{ and }{L}_2=3$ and applies the tribonacci recursion then $L_n=\lfloor {\tau }^n\rceil$ for Template:Tmath Template:OEIS

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, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, … Template:OEIS

Feinberg also coined the term tetranacci.Template:R

The tetranacci constant is the ratio toward which adjacent tetranacci numbers tend. It is the unique positive real root of the polynomial Template:Tmath, approximately Template:Val Template:OEIS, and also satisfies the equation Template:Tmath.

The tetranacci constant can be expressed in terms of radicals by the following expression:

$x=\frac{1}{4}(1+\sqrt{u}+\sqrt{11-u+\frac{26}{\sqrt{u}}})$

where,

$u=\frac{1}{3}(11-56\sqrt[3]{\frac{2}{-65+3\sqrt{1689}}}+2\cdot 2^{\frac{2}{3}}\sqrt[3]{-65+3\sqrt{1689}})$

and $u$ is the real root of the cubic equation Template:Tmath.

Corresponding to the Lucas numbers for the Fibonacci sequence, if one instead starts with $L_0=4$, $L_1=1$, $L_2=3$, and $L_3=7$ and applies the tetranacci recursion then $L_n=\lfloor x^n\rceil$ for Template:Tmath Template:OEIS

Pentanacci numbers

0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, … Template:OEIS

The pentanacci constant is the ratio toward which adjacent pentanacci numbers tend. It is the unique real root of the polynomial Template:Tmath, approximately Template:Val Template:OEIS, and also satisfies the equation Template:Tmath.

Hexanacci numbers

0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, … Template:OEIS

The hexanacci constant is the ratio toward which adjacent hexanacci numbers tend. It is the unique positive real root of the polynomial Template:Tmath, approximately Template:Val Template:OEIS, and also satisfies the equation Template:Tmath.

Heptanacci numbers

0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, … Template:OEIS

The heptanacci constant is the ratio toward which adjacent heptanacci numbers tend. It is the unique real root of the polynomial Template:Tmath, approximately Template:Val Template:OEIS, and also satisfies the equation Template:Tmath.

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, ... Template:OEIS

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, ... Template:OEIS

Infinacci numbers

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.

k-nacci numbers

The Template:Mvarth Template:Mvar-nacci number $F_n^{(k)}$ is the coefficient of $x^n$ in the expansion of the ordinary generating function $f_k(x)=\frac{x^{k-1}}{1-\sum _{j=1}^k{x}^j}=\frac{x^{k-1}(1-x)}{1-2x+x^{k+1}}$ about the point $x=0$.

The limit of the ratio of successive terms of the $k$-nacci series is the root nearest to 2 of the characteristic equation Template:Tmath, which (multiplying both sides by $1-r$) can be expressed as $r+r^{-k}=2$ (Template:OEIS2C, Template:OEIS2C, Template:OEIS2C).

The special case $k=2$ is the traditional Fibonacci series yielding the golden section Template:Tmath.

The above formulas for the ratio hold even for $k$-nacci series generated from arbitrary starting numbers. The ratio approaches 2 in the limit that $k$ increases to infinity.

Let $x=r^{-1}$ be the position of the closest pole of $f_k(x)$. Since the denominator $1-\sum _{j=1}^k{x}^j$ is concave along the positive reals while the convolved version $1-2x+x^{k+1}$ is convex, using an iteration of Newton's method from the approximation of the root $x\approx \frac{1}{2}$ gives an upper bound with the former polynomial and a lower bound with the latter; $1+\frac{1}{2^{k+1}-k-1}<\frac{x}{2}<1+\frac{1}{2^{k+1}-k-2}$, translating to the tight bounds $2-\frac{1}{2^k-\frac{k+1}{2}}<r<2-\frac{1}{2^k-\frac{k}{2}}$.

The negative root of the characteristic equation is in the interval $(-1,0)$ when $k$ is even. This root and each complex root of the characteristic equation has modulus $3^{-k}<|r|<1$.

A series for the positive root $r$ for any $k>0$ is

Template:Tmath.

There is no solution of the characteristic equation in terms of radicals when Template:Math.

The Template:Mvar-th element of the Template:Mvar-nacci sequence is given by

$F_n^{(k)}=\lfloor \frac{r^{n-1}(r-1)}{(k+1)r-2k}\rceil ,$

where $\lfloor \cdot \rceil$ denotes the nearest integer function.

Corresponding to the Lucas numbers for the Fibonacci sequence, if one instead starts with $L_0=k$ and $L_n=2^n-1$ for Template:Tmath, and applies the Template:Tmath-nacci recursion to compute Template:Tmath for Template:Tmath then $L_n=\lfloor r^n\rceil$ for all large enough values of Template:Tmath, where Template:Tmath is the Template:Tmath-nacci constant. Equivalently, one could start with $L_0=k$ and $L_n=-1$ for Template:Tmath, and then apply the Template:Tmath-nacci recursion to compute Template:Tmath for Template:Tmath.

A coin-tossing problem is related to the $k$-nacci sequence. The probability that no $k$ consecutive tails will occur in $m$ tosses of an idealized coin is Template:Tmath. (See Feller's coin-tossing constants.)

Fibonacci word

Template:Main In analogy to its numerical counterpart, the Fibonacci word is defined by:

$F_n:=F(n):=\{\begin{array}{cc}\text{b}& n=0;\\ \text{a}& n=1;\\ F(n-1)+F(n-2)& n>1.\end{array}$

where $+$ denotes the concatenation of two strings. The sequence of Fibonacci strings starts:

Template:Not a typo … Template:OEIS

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 algorithms.

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

$F_n^{(0)}=F_n$

and

$F_n^{(k)}=\sum _{i=0}^n{F}_i{F}_{n-i}^{(k-1)}$

The first few sequences are

$k=1$: 0, 0, 1, 2, 5, 10, 20, 38, 71, … Template:OEIS.

$k=2$: 0, 0, 0, 1, 3, 9, 22, 51, 111, … Template:OEIS.

$k=3$: 0, 0, 0, 0, 1, 4, 14, 40, 105, … Template:OEIS.

The sequences can be calculated using the recurrence

$F_{n+1}^{(k)}=F_n^{(k)}+F_{n-1}^{(k)}+F_n^{(k-1)}$

The generating function of the $k$th convolution is

Template:Tmath.

The sequences are related to the sequence of Fibonacci polynomials by the relation

$F_n^{(k)}=k!F_n^{(k)}(1)$

where $F_n^{(k)}(x)$ is the $k$th derivative of Template:Tmath. Equivalently, $F_n^{(k)}$ is the coefficient of $(x-1{)}^k$ when $F^{(k)}(x)$ is expanded in powers of Template:Tmath.

The first convolution, $F_n^{(1)}$ can be written in terms of the Fibonacci and Lucas numbers as

$F_n^{(1)}=\frac{n{L}_n-F_n}{5}$

and follows the recurrence

Template:Tmath.

Similar expressions can be found for $k>1$ with increasing complexity as $k$ increases. The numbers $F_n^{(1)}$ are the row sums of Hosoya's triangle.

As with Fibonacci numbers, there are several combinatorial interpretations of these sequences. For example $F_n^{(1)}$ is the number of ways $n-2$ can be written as an ordered sum involving only 0, 1, and 2 with 0 used exactly once. In particular $F_4^{(1)}=5$ and 2 can be written Template:Nowrap, Template:Nowrap, Template:Nowrap, Template:Nowrap, Template:Nowrap.

Other generalizations

The Fibonacci polynomials are another generalization of Fibonacci numbers.

The Padovan sequence is generated by the recurrence Template:Tmath.

The Narayana's cows sequence is generated by the recurrence Template:Tmath.

A random Fibonacci sequence can be defined by tossing a coin for each position $n$ of the sequence and taking $F(n)=F(n-1)+F(n-2)$ if it lands heads and $F(n)=F(n-1)-F(n-2)$ 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 Template:Nowrap 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, … Template:OEIS

Since the set of sequences satisfying the relation $S(n)=S(n-1)+S(n-2)$ 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-dimensional. If we abbreviate such a sequence as Template:Tmath, the Fibonacci sequence $F(n)=(0,1)$ and the shifted Fibonacci sequence $F(n-1)=(1,0)$ are seen to form a canonical basis for this space, yielding the identity:

$S(n)=S(0)F(n-1)+S(1)F(n)$

for all such sequences Template:Mvar. For example, if Template:Mvar is the Lucas sequence Template:Nowrap, then we obtain

Template:Tmath.

Template:Mvar-generated Fibonacci sequence

Given an integer $k\ge 2$ , the Template:Mvar-generalized Fibonacci sequence $\{F_n^{(k)}{\}}_{n\in \mathbb{Z}}$ is defined by the recurrence relation

$\begin{array}{c}{F}_n^{(k)}=F_{n-1}^{(k)}+F_{n-2}^{(k)}+\cdots +F_{n-k}^{(k)},\text{for all}n\ge 2,\end{array}$

with initial values $F_{2-k}^{(k)}=\cdots =F_{-1}^{(k)}=F_0^{(k)}=0$ and $F_1^{(k)}=1$.

Sequence	Template:Mvar	OEIS sequence
Fibonacci sequence	6	Template:OEIS link
Pell sequence	12	Template:OEIS link
Jacobsthal sequence	18	Template:OEIS link
Narayana's cows sequence	10	Template:OEIS link
Padovan sequence	15	Template:OEIS link
Third-order Pell sequence	20	Template:OEIS link
Tribonacci sequence	30	Template:OEIS link
Tetranacci sequence	210	Template:OEIS link

Semi-Fibonacci sequence

The semi-Fibonacci sequence Template:OEIS is defined via the same recursion for odd-indexed terms $a(2n+1)=a(2n)+a(2n-1)$ and Template:Tmath, but for even indices Template:Tmath, Template:Tmath. The bisection Template:OEIS link of odd-indexed terms $s(n)=a(2n-1)$ therefore verifies $s(n+1)=s(n)+a(n)$ and is 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, ... Template:OEIS

which occur as Template:Tmath.

External links

• Template:Springer