Convolved Fibonacci Sequences
A convolved Fibonacci sequence is obtained applying a convolution operation to the Fibonacci sequence one or more times. Specifically, define
and
The first few sequences are
- (r=1): 0, 0, 1, 2, 5, 10, 20, 38, 71, … (sequence A001629 in OEIS).
- (r=2): 0, 0, 0, 1, 3, 9, 22, 51, 111, … (sequence A001628 in OEIS).
- (r=3): 0, 0, 0, 0, 1, 4, 14, 40, 105, … (sequence A001872 in OEIS).
The sequences can be calculated using the recurrence
The generating function of the r-th convolution is
The sequences are related to the sequence of Fibonacci polynomials by the relation
where Fn(r)(x) is the r-th derivative of Fn(x). Equivalently, Fn(r) is the coefficient of (x−1)r when Fn(x) is expanded in powers of (x−1).
The first convolution, Fn(1) can be written in terms of the Fibonacci and Lucas numbers as
and follows the recurrence
Similar expressions can be found for r>1 with increasing complexity as r increases. The numbers Fn(1) are the row sums of Hosoya's triangle.
As with Fibonacci numbers, there are several combinatorial interpretations of these sequences. For example Fn(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 F4(1)=5 and 2 can be written 0+1+1, 0+2, 1+0+1, 1+1+0, 2+0.
Read more about this topic: Generalizations Of Fibonacci Numbers