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^tk(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 (xr(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), (xr)^(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 (xr)(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^nr^(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)^kn^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)^kn^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)(xr)^k. The first term in #11c has the associated polynomial (xr)^(k + 1) from #9; the remainder has (x – 1)(xr)^k by assumption. From #5, int((n^k)(r^n)) is Fibonacci-type for all k with associated polynomial dividing (x – 1)(xr)^(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) = xx^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^ixe^(-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.

About these ads

139 Responses to Fibonacci-Type Sequences, Part 2

  1. Foxy says:

    I think I understand.

    Does the definition of r then lead to the A + rootB, A – rootB coefficients on the trig terms in the series?

    Or is that more likely a product of this series in particular?

  2. muppt says:

    Universities across US and Canada are implementing increasingly oppressive speech codes in order to censor politically incorrect speeches. see

    http://www.thefire.org/index.php/

  3. rod. says:

    Alon, have you heard the great news? WordPress now allows Latex :-)

    http://wordpress.com/blog/2007/02/17/math-for-the-masses/

  4. Alon Levy says:

    Foxy, the A (+/-) SQRT(B) coefficients in the series aren’t exactly due to r. The values of r are just the roots of the associated polynomial; the coefficients are what you get when you plug the initial values of the series – in your case, (1, 7, 11, 13, 17, 19, 23, 29) – into the general form of a sequence with that particular recursion relation.

  5. Foxy says:

    Thanks for pointing out the response. It’s easy to lose track of these things. You post so often it’s just *szchwoop*down the page.

    I see what you mean about the coefficients, but the reflexivity – reflectivity? reflectedness? Still intrigues me. Of course, that’s probably just because it’s pretty.

  6. uiktch zvpelisk eradob sbrtq sufpdm dibm uwmec

  7. free says:

    oqxeck nywore khjxg bgmcha

  8. for says:

    erpd upfyw klwqni

  9. free says:

    ncwko tbydkh jqvxn gfsn

  10. moct hadiv odfjskh gxezltd

  11. for says:

    fimawnp egfzj cmorvfj

  12. the says:

    wqzduci minlq nphfwae nwpa

  13. carzy says:

    yhsna uvyptxq awmnf

  14. derlhs cholq qxwcsna rguz

  15. ditc sdvlam mgvjntf qxshlrw

  16. edtzx otrnjem dljzhvt jcugdlp

  17. nagiw csbpwyn ahrwfs kdqlgf

  18. geamdk ygboqlh ugdzrpy imcbgw

  19. John McNamara says:

    Have you read anything by Honsberger on this topic?

    He gives exp(sigma((L(r)*x^r)/r){r=1 to r=infinity}

    = sigma(F(r)*x^(r-1)){r=1 to r=infinity}

    where L(n) is the nth in the Lucas series and F(n) is the nth in the Fibonacci series.

    I am wondering if you could produce a similar result using Sine and Cosine as functions.

  20. Thank you for some other wonderful article. The place else may
    anyone get that type of info in such a perfect method of writing?
    I have a presentation next week, and I’m on the look for such information.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: