Fibonacci-Type Sequences, Part 2

Recall from part 1 that a sequence is said to be of Fibonacci type if it’s given by the recursion relation a(n + t) = k(t)a(n + t – 1) + k(t – 1)a(n + t – 2) + … + k1a(n), with set initial conditions on a1, a2, …, and a(t). Recall also that every such sequence is given by a linear combination of sequences of the form a(n) = (n^k)(r^n), where r is a root of the associated polynomial x^t – k(t)x^(n + t – 1) – … – k1 = 0 and k is a number between 0 and one less than the multiplicity of r.

A Carnival of Mathematics submission that notes how a convoluted sequence that generates all integers not divisible by 2, 3, or 5 has just enough material that Fibonnaci-type sequences are relevant to to prompt me to write a follow up, showing a few additional properties of those sequences.

1. Trivially, a sequence is Fibonacci-type iff it can be written as a sum c1(n^k1)(r1^n) + … + c(m)(n^k(m))(r(m)^n). The only if direction is clear from the calculation in the previous post, while the if direction follows by creating a polynomial for which every r(i) is a root of multiplicity at least k(i) + 1, such as the least common multiple of (x – r(i))^(k(i) + 1) over all i.

2. Every periodic sequence is Fibonacci-type. This is because a periodic sequence is defined by the relation a(n + t) = a(n) for some t, which provides a suitable recursion relation.

3. The sum and difference of two Fibonacci-type sequences are themselves Fibonacci-type. This follows directly from #1, because there is no restriction on the possible values of r(i) and k(i).

4. The product of two Fibonacci-type sequences is Fibonacci-type. To see this, multiply elements of the form (n^k(i))(r(i)^n) pointwise. We have (n^k1)(r1^n)(n^k2)(r2^n) = (n^(k1 + k2))((r1r2)^n).

5. If the associated polynomial of a(n) is f(x) and this of b(n) is g(x), then this of a(n) + b(n) divides the lowest common multiple of f and g. This follows from the fact that if r is a root of the new associated polynomial of multiplicity k + 1, then (n^k)(r^n) appears somewhere in a(n) + b(n), so it must appear in a(n) or b(n).

6. A Fibonacci-type sequence can be continued to zero and negative values of n by reversing the recursion relation to a(n) = (a(n + t) – k(t)a(n + t – 1) – … – k2a(n + 1))/k1.

7. Specifying any t distinct points of a Fibonacci-type sequence and its recursion relation is enough to determine it. Usually the points specified are a1, a2, …, and a(t), but any t points will suffice, since they will provide t linear equations using the basis elements (n^k)(r^n) that allow recovering all values of c(i). These points can of course correspond to negative values of n.

8. Given any Fibonacci-type sequence a(n), the shifted sequence b(n) = a(n + 1) is Fibonacci-type. This is obvious from the recursion relations, which are invariant under shifting. Changing n to n + 1 changes (n^k)(r^n) to ((n + 1)^k)(r^(n + 1)) = r((n + 1)^k)(r^n) = r(n^k + kn^(k – 1) + (k(k – 1)/2)n^(k – 2) + … + kn + 1)(r^n), which corresponds to the same polynomial as (n^k)(r^n), (x – r)^(k + 1). Using #6, this also applies to the shifted sequence b(n) = a(n – 1), except of course with a slightly modified change to the basis elements.

9. It makes sense to define the derivative of a(n), a‘(n), as a(n) – a(n – 1); it shares some characteristics with the derivative of a function. If a(n) is Fibonacci-type, then so is a‘(n) from #3 and #8. By observing the action of differentiation on each (n^k)(r^n), it follows that a‘(n) obeys the same recursion relations as a(n).

10. The general root r of the associated polynomial of a(n) appears in the associated polynomial of a‘(n) with the same multiplicity. That the multiplicity in a‘(n) is no higher than in a(n) follows from #9. For the other direction, if the multiplicity of r in a(n) is k + 1, and the coefficient of (n^k)(r^n) in a(n) is the nonzero number c1, then the coefficient of (n^k)(r^n) in a‘(n) is c1(r – 1), from #6. But if r = 1, then the multiplicity goes down by 1, since r – 1 = 0. Indeed, observe that n^k – (n – 1)^k = kn^(k – 1) – (k(k – 1)/2)n^(k – 2) + … + (-1)^(k + 1) is a polynomial of degree k – 1.

11. It makes sense to define the inverse differentiation operator, integration, by int(a)(n) = a1 + a2 + a3 + … + a(n). It’s not difficult to see that int(a)'(n) = a(n). If a(n) is Fibonacci-type then so is int(a)(n), with the same associated polynomial except that if 1 is a root then its multiplicity goes up by 1. Proving it is complicated, so I’ll do it in stages:

11a. If a(n) = n^k, then int(a)(n) is a polynomial of degree k + 1. For that, let p(n) = c(k + 1)n^(k + 1) + c(k)n^k + … + c0. We want the n^k-coefficient of p(n – 1) to be 1 less than this of p(n), so that c(k + 1)(n^(k + 1) – (n – 1)^(k + 1)) = n^k + q(n) where deg(q) < k; for that, we expand (n – 1)^(k + 1) binomially to get c(k + 1) = 1/(k + 1). By a similar process, we equate the c(k) coefficients to get c(k) = 1/2, and so on until we get c0 = 0. That polynomial was constructed to have the recursion relation p(n + 1) = p(n) + n^k and the initial condition p(0) = 0, so it’s indeed int(a)(n).

11b. If a(n) = r^n and r != 1, then int(a)(n) is a multiple of r^n plus a constant. To see why, note that (r – 1)(r^n + r^(n – 1) + … + 1) telescopes to r^(n + 1) – 1, so that int(r^n) = (r^(n + 1) – 1)/(r – 1) = (r/(r – 1))r^n – 1/(r – 1). That turns a(n) into a Fibonacci-type sequence whose associated polynomial is (x – r)(x – 1). To get rid of the extra root, we need to sum from negative infinity when |r| > 1, i.e. look at (r – 1)(r^n + r^(n – 1) + …) = r^(n + 1). When |r| < 1, we need to instead look at the negative of the sum from n to positive infinity, which will be (r – 1)(-r^n – r^(n + 1) – …) = –r^(n + 1). When |r| = 1, this sum does not converge and is therefore meaningless.

11c. If a(n) = (n^k)(r^n) and r != 1, then int(a)(n) is Fibonacci-type. For that, assume that this is true for all exponents smaller than k, and in particular for all polynomials of degree at most k – 1. Then write rint(a)(n) = r^2 + (2^k)r^3 + … + (n^k)(r^(n + 1)) = r + (2^k)r^2 + (3^k)r^3 + … + ((n + 1)^k)r^(n + 1) – r – (2^k – 1)r^2 – (3^k – 2^k)r^3 – … – ((n + 1)^k – n^k)r^(n + 1). By the definition of int(a)(n), we get (r – 1)int(a)(n) = ((n + 1)^k)r^(n + 1) – r – (2^k – 1)r^2 – (3^k – 2^k)r^3 – … – ((n + 1)^k – n^k)r^(n + 1). The first term is Fibonacci-type by #9, and the sum of the rest is by assumption.

11d. The associated polynomial of int((n^k)(r^n)) is (x – 1)(x – r)^k. The first term in #11c has the associated polynomial (x – r)^(k + 1) from #9; the remainder has (x – 1)(x – r)^k by assumption. From #5, int((n^k)(r^n)) is Fibonacci-type for all k with associated polynomial dividing (x – 1)(x – r)^(k + 1). That division can’t be proper, because only the first term
has the term (n^k)(r^n) while only the remainder has a constant term.

12. The trigonometric functions sin and cos are Fibonacci-type. Note that because pi is irrational, sin(n) is not periodic. However, the identity e^ix = cos(x) + isin(x), derived from considering the Maclaurin expansions e^x = 1 + x + x^2/2 + x^3/3! + …, sin(x) = x – x^3/3! + x^5/5! – …, cos(x) = 1 – x^2/2 + x^4/4! – …, allows us to express sin and cos in terms of exponentials. We get cos(x) = (e^ix + e^(-ix))/2, sin(x) = (e^ix – e^(-ix))/2i. But ((e^i)^x) and ((e^(-i))^x) are Fibonacci-type; hence, so are sin and cos, by #3.

13. Separating a Fibonacci-type sequence into parts results in Fibonacci-type sequences. That is, if a(n) is Fibonacci-type, and b(n) = a(cn + d), then b(n) is Fibonacci-type. To see why, note that this turns (n^k)(r^n) into ((cn + d)^k)(r^(cn + d)) = (c^k)(r^d)((n + d/c)^k)((r^c)^n) where ((n + d/c)^k) is a polynomial in n of degree k.

14. Weaving several Fibonacci-type sequences into one results in a Fibonacci-type sequence. I’ll only prove it when “several” means “two”; the generalization is straightforward enough to be left as an exercise. When a(n) and b(n) are Fibonacci-type and c(n) = a(n/2) for even n and b((n + 1)/2) for odd n, we can use the fact that (-1)^n + 1^n = 2 when n is even and 0 when n is odd to alternatively activate or deactivate the sequence. More precisely, given (n^k)(r^n), note that (((n/2)^k)(SQRT(r)^n) + ((n/2)^k)((-SQRT(r))^n))/2 = ((n/2)^k)(r^(n/2)) when n is even and 0 when n is odd.

15. If a(n) is periodic of period t, then all of its basis elements are of the form r^n with r^t = 1 for all r. This follows from the definition, since the associated polynomial of the sequence is x^t – 1. Now, if r^t = 1, then e^(2pi*i) = 1 implies r^n = e^(2pi*in/t) = cos(2pi*n/t) + isin(2pi*n/t).

The carnival submission takes a sequence with periodic differences and constructs an explicit formula for it with trigonometric, constant, and linear terms. That is immediately a Fibonacci-type sequence from #1 and #11; #15 also shows that the associated polynomial has 1 as a double root, corresponding to the constant and linear terms, and every other 8th root of unity as a simple root, corresponding to each trigonometric term, where the argument is indeed a multiple of pi*n/4.